The giraffe is tired, and he begins to dream.

In his dream, he is falling. He passes through meadows and swirling flocks of sheep. He passes through a sea of stars and skies filled with fiery feathers.

Finally, he stands before a screen. The screen displays a pattern resembling a staircase.

Description

We first provide a formal definition of a staircase.

We call a pair of positive integers $(x,y)$ a cell, and a set of cells $L$ (which may be empty) 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 $(x,y)\in L$, we define the sub-staircase generated by the generating cell $(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 also a staircase. For a staircase $L$, we define the boundary cell count as the number of cells $(x,y)\in L$ such that $x=1$ or $y=1$.

For intuitive understanding, we can arrange all cells on a plane in a grid where the $y$-coordinate increases from left to right and the $x$-coordinate increases from top to bottom; thus, we also refer 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 the cells above and to the left of it are not on the boundary, then the corresponding cells also belong to this staircase. A sub-staircase is the non-empty staircase formed by the cells in the region to the bottom-right of the generating cell, and 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$.

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

Dreams change frequently, so the giraffe may have many such queries, and the staircase may also change. The initial staircase $L$ is empty. For $i\ge1$, let $s_i$ be the largest positive integer such that $(i,s_i)\in L$, or $0$ if no such integer exists. There are 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,\cdots,a$, add $(i,s_i+1),(i,s_i+2),\cdots,(i,s_i+b)$ to $L$.
• Given positive integers $a$ and $b$, remove $b$ cells from the end of all rows from row $a$ onwards (inclusive). If a row has fewer than $b$ cells, remove all of them. Formally, for $i=a,a+1,a+2,\cdots,10^{100}$, remove $(i,s_i),(i,s_i−1),\cdots,(i,s_i−b+1)$ from $L$ (ignore if the cell does not exist).
• Given a positive integer $u$, undo the previous $u$ operations, restoring the staircase to the state before those $u$ operations. It is guaranteed that these $u$ operations were either queries or insertions at the end of rows. Specifically, assuming this is the $t$-th operation, we have $t>u$, and the $(t-1)$-th, $(t-2)$-th, $\cdots, (t-u)$-th operations were all queries or insertions (the first type of modification). You only need to restore the staircase to the state before the $(t-u)$-th operation (you should, of course, preserve the outputs of the queries).

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

Input

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

The next $m$ lines each describe one of the four operations, the meanings of which are detailed in the description. The description consists of a character followed by one or two positive integers separated by spaces:

• + a b: Insert $b$ cells at the end of the first $a$ rows.
• - a b: Remove $b$ cells from the end of all rows from row $a$ onwards (inclusive).
• R u: Undo the previous $u$ operations, restoring the staircase to the state before those $u$ operations. It is guaranteed that these $u$ operations exist and were all queries or insertions at the end of rows, meaning the $u$ lines preceding this one all started with + or ?.
• ? q: Query whether there exists a sub-staircase with a boundary cell count equal to $q$. If so, provide any valid generating cell. It is guaranteed that $q$ is a factor of the current boundary cell count.

Output

For each query (? operation), output a single line.

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

Examples

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

Output 1

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

Note 1

The staircase after each modification is shown in the figure below (the arrangement is the same as in the description, with cell numbering omitted). Note that the undo operation only actually undid one + operation. There are multiple valid solutions for the sample; the output provided is just one valid output.

Input 2

(See provided file)

Output 2

(See provided file)

Input 3

(See provided file)

Output 3

(See provided file)

Input 4

(See provided file)

Output 4

(See provided file)

Input 5

(See provided file)

Output 5

(See provided file)

Input 6

(See provided file)

Output 6

(See provided file)

Subtasks

For all test data, $1\le m\le3\times10^5$.

• For + and - operations, $1\le a,b\le10^9$.
• For R operations, it is guaranteed that the $u$ immediately preceding operations exist and were all queries or insertions at the end of rows.
• For ? operations, $1\le q\le10^{18}$ and it is guaranteed that $q$ is a factor of the current 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.

Subtask 1 (10 points): $m,a_{\max}\le 1000$.

Subtask 2 (20 points): $m\le 1000$.

Subtask 3 (10 points): $m\le 10000$.

Subtask 4 (20 points): $m\le 40000$.

Subtask 5 (10 points): $m\le 120000$.

Subtask 6 (10 points): Guaranteed that ? operations occur after all + and - operations. No R operations.

Subtask 7 (20 points): No special restrictions.

Note

Please ensure you use appropriate data types to store the results.