You're maintaining 20 variables: \(a, b, c, \dots, r, s, t\). At any moment of time value of any variable is integer between 0 and \(1,000,000,006\), inclusive. All arithmetic operations with variables are modulo \(1,000,000,007\). Initially (at moment 0) all variables are set to 0. At some moments of time, you get queries. Queries have 5 different types:

\(\textrm{"? x"}\) print value of variable x.
\(\textrm{"= x y"}\) write value of variable y to variable x.
\(\textrm{"! x c"}\) set variable x to c.
\(\textrm{"+ x c"}\) add c to variable x.
\(\textrm{"* x c"}\) multiply variable x by c.

Also with each query you are given a positive integer --- time when you need to apply this query to variables. Times can go in arbitrary order. See sample for further clarification.

Input Format:
First line contain one integer q --- number of queries.
Next q lines contains queries. i-th query starts with integer \(t_i\) --- time this query should be made at.
Then one of 5 query goes in format, described in the statement.

Output Format:
For each query of the first time print the corresponding value.

Constraints:
\(1 \leqslant q \leqslant 100,000.\)
\(1 \leqslant t_i \leqslant 1,000,000,000.\)
All \(t_i\) are distinct.
In all queries, \(x, y \in \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t \}.\)
Also in all queries \(0 \leqslant c \leqslant 1,000,000,006.\)

Scoring:
20 points
Additionally \(q \leqslant 5,000\).
20 points
Additionally, in all queries, \(x = y = a\).
Also queries only of types \(\textrm{*, +, ?}\) are present.
20 points
Additionally, in all queries \(x, y \in \{a, b, c, d, e\}\).
40 points
No additional constraints.