시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 65 18 15 25.000%

문제

JuQueen is the super computer with the best performance allover Germany. It is on rank 8 in the famous top500 list with its 458 752 cores. It draws a lot of energy (up to 2 301 kW), so we want to reduce that by underclocking the unused cores. The cluster scheduling algorithm which is in charge of distributing jobs over the nodes and cores of a cluster will issue the following 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 range [A,B] by S steps
  • state X returns the current state of core X

To be safe for the future, your program should be able to handle 4 587 520 cores. The initial frequency for each core is 0.

입력

The input contains a single test case. It starts with a line containing three integers C, N, and O, where C is the number of cores (1 ≤ C ≤ 4 587 520) to manage, N is the number of frequency steps for each core (1 ≤ N ≤ 10 000) and O is the number of operations in the test program (1 ≤ O ≤ 50 000). Then follow O lines, each containing one command as described above. X, A and B are 0-based IDs of the cores (0 ≤ A, B, X < C; A ≤ B). S is an integer number of steps, possibly negative (−N ≤ S ≤ +N).

Both, the change and the groupchange command will increase (or decrease) in single steps and stop as soon as one core in the group reaches the minimal (0) or maximal frequency (N).

출력

Output one line for every operation in the input. For change and groupchange print the changed number of steps, for state print the current state.

예제 입력

10 10 5
state 0
groupchange 2 9 7
state 9
groupchange 0 2 10
change 0 -5

예제 출력

0
7
7
3
-3

예제 입력 2

4587520 10000 5
groupchange 0 4587010 9950
groupchange 23 4587000 42
groupchange 4710 4587001 -1000
state 1234560
groupchange 6666 3060660 10000

예제 출력 2

9950
42
-1000
8992
1008

힌트