15061506 SUSTech Online Judge
Problem 1506 --Irotas's Robot

1506: Irotas's Robot

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 288  Solved: 51
[Submit][Status][Web Board]

Description

A robot resides in a linear field, where positions are from left to right labelled as $$0, 1, 2, \dots, C-1, C$$.

The robot may accept an integer $$k$$ as command. Suppose the robot is at position $$x$$. Its reponse will be moving $$k$$ units rightwards as long as it stays within $$[0, C]$$. Note that $$k$$ may be negative, meaning that the robot will move $$|k|$$ units leftwards. The final position is described as $$x' = \max(0, \min(C, x + k))$$.

The central computer stores an operation sequence $$\{y_1, y_2, \dots, y_N\}$$, on which the robot will execute sequentially. Irotas, the researcher, may also insert a new command to the sequence, or remove a command from it. Meanwhile, you need to answer Irotas's question every time she asked so: where will the robot eventually be if she initially places the robot at $$x_0$$?

Formally speaking, let $$N$$ denote the length of the operation sequence at any time. You are asked to support the following actions:

1. Irotas inserted a new command $$y_{new}$$ into the operation sequence, right before $$y_k$$ ($$k \in [1, N + 1]$$). If $$k=N+1$$, the command is inserted at the end of the sequence.
2. Irotas removed $$y_k$$ from the operation sequence ($$k \in [1, N]$$).
3. Irotas gives you $$x_0$$ as the initial position and queries the eventual position.

Input

The first line contains two integers $$C, N$$.

The second line contains $$N$$ integers, representing $$y_1, y_2, \dots, y_N$$.

The third line contains an integer $$M$$, denoting the number of actions to perform.

For the following $$M$$ lines, each line is in one of the three formats, denoting the three actions respectively:

1. $$\text{ins}\ k\ y_{new}$$
2. $$\text{rem}\ k$$
3. $$\text{ask}\ x_0$$

输入限制

$$C, x_0 \in [0, 10^9]$$

For the operation sequence $$\{y_1, y_2, \dots, y_N\}$$, at any time we have:

• $$0 \le N \le 2 \times 10^5$$ (i.e. "remove" operation will not occur when $$N = 0$$, "insert" operation will not occur when $$N = 2 \times 10^5$$)
• $$|y_i| \le 10^9$$
• $$0 \le M \le 10^5$$

Output

For each action 3, output one line containing a single number, representing the final result.

Sample Input

10 3
4 -5 2
5
rem 1
ins 2 -3
ask 7

Sample Output

7
4
2

[Submit][Status]