Hide

Problem C
Accounting

Languages en sv

Erika the economist studies economic inequality. Her model starts in a situation where everybody has the same amount of money. After that, people’s wealth changes in various complicated ways.

Erika needs to run a simulation a large number of times to check if her model works. The simulation consists of N people, each of whom begins with 0 kroners. Then Q events happen, of three different types:

  1. An event of type “SET i x” means that the ith person’s wealth is set to x.

  2. An event of type “RESTART x” means that the simulation is restarted, and everybody’s wealth is set to x.

  3. An event of type “PRINT i” reports the current wealth of the ith person.

Unfortunately, Erika’s current implementation is very slow; it takes far too much time to keep track of how much money everybody has. She decides to use her algorithmic insights to speed up the simulation.

Input

The first line includes two integers N and Q, where 1N106 and 1Q2105. The following Q lines each start with a string that is either “SET”, “RESTART”, or “PRINT”. There is guaranteed to be at least one event of type “PRINT”.

If the string is “SET” then it is followed by two integers i and x with 1iN and 0x104. If the string is “RESTART” then it is followed by an integer x with 0x104. If the string is “PRINT” then it is followed by an integer i with 1iN.

Output

For each event of type “PRINT”, write the ith person’s capital.

Sample Input 1 Sample Output 1
3 5
SET 1 7
PRINT 1
PRINT 2
RESTART 33
PRINT 1
7
0
33
Sample Input 2 Sample Output 2
5 7
RESTART 5
SET 3 7
PRINT 1
PRINT 2
PRINT 3
PRINT 4
PRINT 5
5
5
7
5
5
Hide

Please log in to submit a solution to this problem

Log in