Problem Background

The giraffe is tired and begins to dream.

In his dream, he falls. He passes through meadows, swirling flocks of sheep, star-filled seas, and skies filled with fiery feathers.

Finally, he stands before a screen displaying a pattern resembling stairs.

Problem Description

We start by providing some formal definitions related to stairs.

A pair of positive integers $(x, y)$ is called a cell. A set of cells $L$ (which can be empty) is called a staircase if and only if it satisfies the following two conditions:

• If $(x, y) \in L$ and $x > 1$, then $(x-1, y) \in L$.
• If $(x, y) \in L$ and $y > 1$, then $(x, y-1) \in L$.

For a staircase $L$ and a cell $(x, y) \in L$, we define the sub-staircase generated by $(x, y)$ as

$$ \{(a-x+1, b-y+1) \mid (a,b) \in L, a \ge x, b \ge y\} $$

It is easy to prove that this set is still a staircase. For a staircase $L$, we define the boundary cell count as the number of cells $(x, y) \in L$ that satisfy $x = 1$ or $y = 1$.

For easier understanding, we provide an intuitive explanation. On a plane, we can arrange all cells in a grid where the $y$ coordinate increases from left to right and the $x$ coordinate increases from top to bottom, thus referring to $(x, y)$ as the cell in the $x$-th row and $y$-th column.

Under this interpretation, if a cell belongs to a staircase and neither its top nor left is a boundary, then the corresponding cell also belongs to the staircase. A sub-staircase is the non-empty staircase formed by the cells in the bottom-right region of the generating cell. The boundary cell count of a staircase is the total number of cells on the top or left boundary.

As shown in the figure below, $(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (4,1), (5,1)$ form a valid staircase. The boundary cell count of this staircase is $8$, and the boundary cell count of the sub-staircase generated by $(1,3)$ is $4$.

The giraffe is curious after seeing the staircase on the screen. He first calculates the boundary cell count $p$ of this staircase and specifies a positive integer factor $q$ of $p$. He wants to know if there is a sub-staircase with a boundary cell count equal to $q$. If so, he hopes you can provide any such generating cell.

Dreams often change, so the giraffe may have many such queries, and the staircase may also change. The initial staircase $L$ is empty. For $i \ge 1$, let $s_i$ be the largest positive integer such that $(i, s_i) \in L$, or $0$ if it does not exist. There will be several modifications of three types:

• Given positive integers $a$ and $b$, insert $b$ cells at the end of the first $a$ rows. Formally, for $i = 1, 2, \dots, a$, add $(i, s_i+1), (i, s_i+2), \dots, (i, s_i+b)$ to $L$.
• Given positive integers $a$ and $b$, remove $b$ cells from the end of all rows including and after the $a$-th row, or remove all if there are not enough cells. Formally, for $i = a, a+1, a+2, \dots, 10^{100}$, remove $(i, s_i), (i, s_i-1), \dots, (i, s_i-b+1)$ from $L$ (ignore those that do not exist).
• Given a positive integer $u$, undo the previous $u$ operations, restoring the staircase to its state before these $u$ operations. Ensure these $u$ operations exist and are all queries or insertions at the end of rows. Specifically, if this operation is the $t$-th operation, we must have $t > u$, and the operations $t-1, t-2, \dots, t-u$ are all queries or insertions at the end of rows (i.e., the first type of modification). You only need to restore the staircase to its state before the $t-u$-th operation (of course, you should keep the outputs of the queries).

It can be proven that the set obtained after each modification is still a staircase.

Input Format

The first line of the input data contains a positive integer $m$, representing the total number of operations.

The next $m$ lines each describe one of four types of operations, with detailed meanings as described in the problem description section. The description consists of a character and one or two positive integers separated by spaces, specifically:

• + a b: Insert $b$ cells at the end of the first $a$ rows.
• - a b: Remove $b$ cells from the end of all rows including and after the $a$-th row, or remove all if there are not enough cells.
• R u: Undo the previous $u$ operations, restoring the staircase to its state before these $u$ operations. Ensure these $u$ operations exist and are all queries or insertions at the end of rows, i.e., the lines before this line all start with + or ?.
• ? q: Query whether there is a sub-staircase with a boundary cell count equal to $q$, and if so, provide any valid generating cell. Ensure $q$ is a factor of the current staircase's boundary cell count.

Output Format

For each query (? operation), output one line.

If there is a sub-staircase with a boundary cell count equal to $q$, output one line with two positive integers x y, representing a valid generating cell $(x, y)$. Otherwise, output one line with two -1s separated by a space.

Sample Input and Output

Sample Input #1

18
+ 5 1
+ 2 1
? 3
+ 3 2
? 4
? 4
+ 4 1
? 3
R 3
- 2 2
? 3
- 1 1
? 2
? 4
- 1 2
? 1
- 9 9
? 1

Sample Output #1

3 1
1 3
2 2
2 4
2 1
1 2
1 1
1 1
1 1

Sample Input #2

See attachment stairs2.in

Sample Output #2

See attachment stairs2.ans

Sample Input #3

See attachment stairs3.in

Sample Output #3

See attachment stairs3.ans

Sample Input #4

See attachment stairs4.in

Sample Output #4

See attachment stairs4.ans

Sample Input #5

See attachment stairs5.in

Sample Output #5

See attachment stairs5.ans

Sample Input #6

See attachment stairs6.in

Sample Output #6

See attachment stairs6.ans

Notes

[Sample Explanation #1]

The staircase after each modification operation is shown in the figure below (arranged as described in the problem, omitting the numbering of each cell). Note that the undo operation actually only undid one + operation. There are multiple valid solutions for the sample, and the provided output is just one valid output.

[Data Range]

For all test data, $1 \le m \le 3 \times 10^5$.

• For + and - operations, $1 \le a, b \le 10^9$.
• For R operations, ensure the previous $u$ operations exist and are all queries or insertions at the end of rows.
• For ? operations, $1 \le q \le 10^{18}$ and ensure $q$ is a factor of the current staircase's boundary cell count.

Let $a_{\max}$ be the maximum value of $a$ in all + and - operations, and $b_{\max}$ be the maximum value of $b$ in all + and - operations.

The special properties in the additional restrictions are as follows:

• Special Property A: ? operations occur after all + and - operations. There are no R operations.
• Special Property B: There are no - operations.

[Hint]

Please use appropriate data types to store the results.

见题面 Input 部分

见题面 Output 部分