Retroactive Integers
Tag(s):

## Data Structures, Data Structures, Matrices, Medium-Hard, Segment tree

Problem
Editorial
Analytics

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:

1. $\textrm{"? x"}$ print value of variable x.
2. $\textrm{"= x y"}$ write value of variable y to variable x.
3. $\textrm{"! x c"}$ set variable x to c.
4. $\textrm{"+ x c"}$ add c to variable x.
5. $\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

SAMPLE INPUT
8
10 ? e
20 = b a
30 * b 10
40 + b 1
60 ? b
5 ! a 10
70 ? b
25 ? b

SAMPLE OUTPUT
0
1
101
10

Explanation
1. No queries added before time $10$, so value of e is 0.
2. From moment $20$, $b=a$.
3. From moment $30$, $b=10a$.
4. From moment $40$, $b=10a+1$.
5. At moment $60$: $b = 10a + 1 = 10 \cdot 0 + 1 = 1$.
6. From moment 5, $a = 10$.
7. So, at moment $70$, $b=10a + 1 = 10\cdot 10 + 1 = 101$ because a changed its value at moment 5.
8. At moment $25$: $b = a = 10$.
Time Limit: 7,0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Basic Math
• Algorithms > Graphs