JuQueen

JuQueen is the highest performing supercomputer in Germany. It has 458,752 cores and sits at rank 8 on the top500 list. Its power draw goes up to 2,301 kW, so the operators want to cut it by underclocking the cores that are idle.

The cluster scheduler that spreads jobs over the nodes and cores issues these three speedstepping commands.

• change X S changes the frequency of core X by S steps.
• groupchange A B S changes the frequency of every core in the range [A, B] by S steps.
• state X reports the current step of core X.

To stay useful on larger machines, your program has to handle up to 4,587,520 cores. Every core starts at step 0.

The input holds a single test case. The first line has three integers C, N, and O. C is the number of cores to manage ($1 \le C \le 4587520$), N is the number of frequency steps one core can take ($1 \le N \le 10000$), so the step of each core is between 0 and N, and O is the number of commands in the test program ($1 \le O \le 50000$). Each of the next O lines holds one command as described above.

X, A and B are 0-based core ids with $0 \le A, B, X < C$ and $A \le B$. S is an integer that may be negative, with $-N \le S \le N$.

Both change and groupchange move the affected cores one step at a time and stop the moment one of them reaches the lowest step 0 or the highest step N. groupchange moves every core of the range together, so once one core in the range hits a bound the other cores stop where they are.

Print one line for every command in the input. For change and groupchange print the number of steps actually applied, including its sign. Print 0 when no step could be applied. For state print the current step of that core.