Problem Statement

There are sequences $a_i, b_i (0 \leq i \leq n)$ defined by recurrences.

$a_{i+1} = x_i b_i^2 + a_i$
$b_{i+1} = y_i b_i + 1$
$a_0 = b_0 = 1$

$x_i, y_i (0 \leq i < n)$ are the $2 n$ parameters of the recurrences. Their initial values are $0$.
Process $q$ queries of the following types.

(1) $x$ $i$ $v$
Change $x_i$ to $v$.
(2) $y$ $i$ $v$
Change $y_i$ to $v$.
(3) $a$ $i$
Output the remainder of $a_i$ divided by $10^9+7$.

Input

$n$
$q$
$query_1$
$\vdots$
$query_q$

All inputs are integers.

$1 \leq n \leq 100000$
$1 \leq q \leq 20000$

Query x
x $i$ $v$
$0 \leq i < n$
$0 \leq v \leq 100000$

Query y
y $i$ $v$
$0 \leq i < n$
$0 \leq v \leq 100000$

Query a
a $i$
$0 \leq i \leq n$

It is guaranteed that there is at least one query a.

Output

Print a newline after each query a.

Sample

2
7
a 2
x 1 1
y 0 3
y 1 2
a 2
y 0 0
a 2

1
17
2

4
17
x 3 67829
x 2 98198
y 2 18912
y 3 67274
x 3 7010
a 1
x 0 9635
a 0
a 3
x 3 5394
a 1
a 4
y 1 3076
a 3
x 1 8612
y 1 55697
a 4

1
1
107834
9636
442357517
731695075
252637976