B. Pinball
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are two horizontal straight lines $$$y = 0$$$ and $$$y = H$$$ on the 2-dimensional plane. Between the two lines there are initially $$$n$$$ tiny wooden boards which can be regarded as single points. The $$$i$$$-th wooden board is located at $$$(x_i, y_i)$$$.

Maintain $$$q$$$ operations of the following three types.

  • $$$+$$$ $$$x$$$ $$$y$$$: Add a wooden board located at $$$(x, y)$$$ to the plane.
  • $$$-$$$ $$$x$$$ $$$y$$$: Remove the wooden board located at $$$(x, y)$$$ from the plane.
  • $$$?$$$ $$$x$$$ $$$y$$$ $$$v_y$$$ $$$g$$$: A pinball is released from $$$(x, y)$$$.

    Let $$$\overrightarrow{v} = (v_x, v_y)$$$ be the velocity of the ball (that is to say, if the ball is currently located at $$$(x, y)$$$ it will move to $$$(x + v_x\epsilon, y + v_y\epsilon)$$$ after $$$\epsilon$$$ seconds). If $$$g \ge x$$$ then $$$v_x = 1$$$, otherwise $$$v_x = -1$$$, while $$$v_y$$$ is given by the query. The value of $$$v_y$$$ is either $$$1$$$ or $$$-1$$$.

    When the ball hits a wooden board or one of the two horizontal straight lines, $$$v_y$$$ will be reversed (that is, $$$v_y$$$ becomes $$$-v_y$$$) while $$$v_x$$$ remains unchanged.

    Calculate the $$$y$$$ coordinate of the pinball when its $$$x$$$ coordinate equals to $$$g$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$) indicating the number of test cases. For each test case:

The first line contains three integers $$$H$$$, $$$n$$$ and $$$q$$$ ($$$2 \le H \le 10^9$$$, $$$1 \le n, q \le 10^5$$$) indicating the position of the upper horizontal straight line, the number of initial wooden boards and the number of operations.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$, $$$1 \le y_i \lt H$$$) indicating the position of the $$$i$$$-th wooden board.

For the following $$$q$$$ lines, the $$$i$$$-th line first contains a character $$$op$$$ ($$$op \in \{+, -, ?\}$$$) indicating the type of the $$$i$$$-th operation.

  • If $$$op = +$$$ then two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le 10^9$$$, $$$1 \le y \lt H$$$) follow, indicating the position of the wooden board to be added. It's guaranteed that there is currently no board located at $$$(x, y)$$$.
  • If $$$op = -$$$ then two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le 10^9$$$, $$$1 \le y \lt H$$$) follow, indicating the position of the wooden board to be removed. It's guaranteed that there is currently a board located at $$$(x, y)$$$.
  • If $$$op = ?$$$ then four integers $$$x$$$, $$$y$$$, $$$v_y$$$ and $$$g$$$ ($$$1 \le x, g \le 10^9$$$, $$$1 \le y \lt H$$$, $$$v_y \in \{-1, 1\}$$$) follow, indicating the initial position of the pinball, the initial velocity along the $$$y$$$-axis of the pinball and the target $$$x$$$-coordinate. It's guaranteed that there is currently no board located at $$$(x, y)$$$.

It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$q$$$ of all test cases will exceed $$$2 \times 10^5$$$.

Output

For each operation of the third type output one line containing one integer indicating the answer.

Example
Input
2
5 2 8
4 2
6 4
? 10 4 -1 3
+ 8 2
? 3 3 -1 12
? 3 1 1 12
- 4 2
? 3 3 -1 12
? 3 1 1 12
? 7 3 1 6
10 1 2
5 5
? 9 2 1 9
? 9 2 -1 9
Output
1
4
2
2
4
4
2
2
Note

We illustrate the queries of the first sample test case as below. Wooden boards are represented as diamonds.