Retroactive Integers

★★★★★

0 votes

Approved, Data Structures, Matrix, Medium, Segment Trees

Details

Problem

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.

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

Time Limit: 7

Memory Limit: 1024

Source Limit:

Explanation

No queries added before time $10$ , so value of e is 0.
From moment $20$ , $b=a$ .
From moment $30$ , $b=10a$ .
From moment $40$ , $b=10a+1$ .
At moment $60$ : $b = 10a + 1 = 10 \cdot 0 + 1 = 1$ .
From moment 5, $a = 10$ .
So, at moment $70$ , $b=10a + 1 = 10\cdot 10 + 1 = 101$ because a changed its value at moment 5.
At moment $25$ : $b = a = 10$ .

Contributers:

Artsem Zhuk

Lewin Gan