Quick DFS

On the infinite square grid a cell is a pair of integers \((x,y)\); two cells are adjacent if they differ by \(1\) in exactly one coordinate.

A region \(R\) is given as the union of \(n\) axis-parallel rectangles; the \(i\)-th of them consists of all cells \((x,y)\) with \(x_{i,1}\le x\le x_{i,2}\) and \(y_{i,1}\le y\le y_{i,2}\). (Note that the rectangles are not necessarily disjoint.)

Every region in this task has the following three properties:

• \(R\) contains the origin: \((0,0)\in R\);
• \(R\) is connected: any two of its cells are joined by a path of adjacent cells that belong to \(R\);
• \(R\) is column-convex: whenever \((x,y_1)\in R\) and \((x,y_2)\in R\), also \((x,y)\in R\) for every \(y\) between \(y_1\) and \(y_2\). In other words, no column of \(R\) has a hole.

A robot explores the region using depth-first search, started by visit(0, 0):

visit(x, y):
    append (x, y) to the visit order and mark it visited
    # try going up, down, right, and then left, in this specific order:
    for (dx, dy) in [ (0, +1), (0, -1), (+1, 0), (-1, 0) ]:
        if (x + dx, y + dy) belongs to R and is not visited yet:
            visit(x + dx, y + dy)

Since \(R\) is connected, every cell is appended exactly once, so the visit order is a permutation of the cells of \(R\). The time of a cell is its position in that order, indexing from \(1\).

Task

Answer \(q\) queries of two kinds:

• 1 k: output the coordinates of the cell visited at time \(k\)
• 2 x y: output the time at which the cell \((x,y)\) is visited.

Input format

The first line of the input contains the number \(t\) of test cases. The specified number of test cases follows, one after another. Each test case looks as follows:

• The first line contains the integers \(n\) and \(q\).
• Each of the next \(n\) lines contains four integers \(x_{i,1}\), \(y_{i,1}\), \(x_{i,2}\), \(y_{i,2}\) describing one rectangle (\(x_{i,1}\le x_{i,2}\), \(y_{i,1}\le y_{i,2}\)).
• Each of the next \(q\) lines contains one query, in one of the two forms above.

All coordinates are between \(-10^9\) and \(10^9\).

The rectangles are always chosen so that their union \(R\) has the three properties listed above.

In a query of the first kind \(1\le k\le |R|\), where \(|R|\) is the number of cells of the region.

In a query of the second kind it is guaranteed that \((x, y)\in R\).

Output format

For every query, in the order in which they are given, output one line: two integers (the coordinates of the cell) for a query of the first kind, one integer (the time) for a query of the second kind. Both answers are uniquely determined.

Subproblem Q1 (12 points, public)

Input file: Q1.in

Constraints: \(t=100\); in each test case \(n\le 200\), \(q\le 200\) and the region has at most \(2\cdot10^5\) cells.

Subproblem Q2 (18 points, secret)

Input file: Q2.in

Constraints: \(t=100\); in each test case \(n=1\) (the region is a single rectangle) and \(q\le 2000\).

Subproblem Q3 (30 points, secret)

Input file: Q3.in

Constraints: \(t=100\); in each test case \(n\le 2000\) and \(q\le 2000\); the sum of \(n\) over all test cases is at most \(10^5\) and the sum of \(q\) is at most \(1.2\cdot10^5\).

Subproblem Q4 (40 points, secret)

Input file: Q4.in

Constraints: \(t=40\); in each test case \(n\le 10^5\) and \(q\le 10^5\); the sum of \(n\) over all test cases is at most \(3\cdot10^5\) and the sum of \(q\) is at most \(2\cdot10^5\).

Examples

2
4 6
-1 -1 1 2
2 2 3 5
4 0 5 3
-1 2 5 2
1 1
1 9
1 13
1 28
2 -1 2
2 4 1
1 3
0 0 3 1
1 8
2 3 0
2 0 1

0 0
-1 -1
2 2
4 1
12
28
3 0
8
2

The region of the first test case, with the time of visiting given in every cell of \(R\):

y\x|  -1   0   1   2   3   4   5
---+-----------------------------
 5 |   .   .   .  16  17   .   .
 4 |   .   .   .  15  18   .   .
 3 |   .   .   .  14  19  22  23
 2 |  12   3   4  13  20  21  24
 1 |  11   2   5   .   .  28  25
 0 |  10   1   6   .   .  27  26
-1 |   9   8   7   .   .   .   .

Note that the region \(R\) for this test case would remain exactly the same if we only used the first three of the four rectangles given in the input.