Sub‐Staircase Boundary Query

A staircase is defined as a set of grid cells L (possibly empty) with coordinates (x, y) (with x, y positive integers) satisfying:

• If (x, y) ∈ L and x > 1 then (x-1, y) ∈ L.
• If (x, y) ∈ L and y > 1 then (x, y-1) ∈ L.

For any cell (x,y) ∈ L (called the generating cell), the sub‐staircase generated by it is defined as \[ \{(a-x+1, b-y+1)\mid (a,b) \in L,\; a\ge x,\; b\ge y\}\] which is easy to show is still a staircase.

The boundary cell count of a staircase is the number of cells in L that lie on the top row (i.e. with x=1) or on the leftmost column (i.e. with y=1). Equivalently, if the staircase is viewed as contiguous cells in each row (that is, row i contains cells (i,1),(i,2),…, (i,s_i) for some s_i ≥ 0), then the conditions force s_1 ≥ s_2 ≥ s_3 ≥ … and the boundary count is p = s_1 + N - 1 where N is the number of nonempty rows (i.e. rows with s_i > 0). (Note that cell (1,1) is counted only once.)

Given the current staircase L (initially empty) maintained as follows. For each row i ≥ 1, let s_i denote the current number of cells in that row (if no cell exists in row i then s_i = 0). Clearly, the staircase property forces that s_1 ≥ s_2 ≥ s_3 ≥ ….

You are to process a sequence of operations. There are four types of operations:

1. Insert: 1 a b — For each row i=1,2,…,a, append b new cells to the end. Formally, for each i=1,…,a, set s_i = s_i + b (if row i does not exist, consider s_i initially as 0).
2. Remove: 2 a b — For every row starting from row a (that is, for all i ≥ a), remove b cells from the end. If a row has fewer than b cells, remove all cells (set s_i = 0).
3. Undo: 3 u — Revert the staircase to the state before the last u operations. It is guaranteed that the u operations being undone are all either insert operations or query operations (queries do not change the state). (Note that removal operations are not undoable.)
4. Query: 4 q — First, note that the current staircase has boundary count p = s_1 + N - 1 (where N is the number of nonempty rows). It is guaranteed that the given positive integer q is a divisor of p. The query asks whether there exists a sub‐staircase of L (generated by some cell (x,y) with 1 ≤ y ≤ s_x) whose boundary cell count is exactly q. If yes, output any such generating cell (x, y); otherwise, output -1 (though it can be shown a solution exists under the given conditions).

The sub‐staircase generated by cell (x,y) has row structure given by: its first row has s_x - y + 1 cells, and for i ≥ 1 the i-th row of the sub‐staircase has max(0, s_{x+i-1} - y + 1) cells. Its boundary count is computed similarly, i.e. (s_x - y + 1) + r - 1 where r is the largest integer such that for all j = 0,1,…,r-1 we have s_{x+j} ≥ y (and if x+r exists then s_{x+r} < y).

Process all operations in order. For each query operation, output the answer on a separate line.

Input Format: The first line contains an integer T, denoting the number of operations. Each of the next T lines describes an operation in one of the following formats:

• 1 a b for an insert operation.
• 2 a b for a remove operation.
• 3 u for an undo operation.
• 4 q for a query.

Output Format: For each query operation, output either two space‐separated integers x y representing the coordinates of a generating cell whose sub‐staircase has boundary count exactly q, or output -1 if no such cell exists.

inputFormat

The first line contains a single integer T (the number of operations).

Each of the next T lines contains an operation in one of the following formats:

• 1 a b — Insert operation.
• 2 a b — Remove operation.
• 3 u — Undo operation.
• 4 q — Query operation.

outputFormat

For each query operation (operation type 4), output on a separate line either two integers x and y (the coordinates of the generating cell) or -1 if no valid sub‐staircase exists.

sample

4
1 3 2
4 2
2 2 1
4 1

2 2
1 2

</p>