#389 Daeshin High School and Queries

Statement

Statement language

The main building of Daejeon Daeshin High School has $4$ floors, and each floor has $N$ classrooms. The floors are numbered $1$ through $4$ from bottom to top. On each floor, the classrooms are numbered $1$ through $N$ from left to right.

Initially, the discomfort value of every classroom is $0$ . Process the following queries.

1 $a$ $b$ : Construction occurs in classroom $b$ on floor $a$ . Increase the discomfort value of that classroom and every vertically or horizontally adjacent classroom by $1$ . Positions outside the building are ignored.
2 $a$ : Print the number of a classroom with maximum discomfort on floor . If several classrooms have the same maximum discomfort, print the smallest classroom number.

After all queries, select a classroom with maximum discomfort in the entire building. If several classrooms have the same maximum discomfort, choose the one on the lowest floor. If there is still a tie, choose the one with the smallest classroom number.

Print the answers to all type 2 queries and the final selected classroom.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For every type 2 query in every test case, print the required classroom number on its own line.

After processing all queries of each test case, print the floor number and classroom number of the final selected classroom, separated by a space.

Constraints

$1 \leq T \leq 1\,000$ .
$1 \leq N \leq 1\,000$ .
$1 \leq Q \leq$ .

Subtasks

#	Score	Constraints
1	28	The sum of $N$ over all test cases does not exceed $30$ . The sum of $Q$ over all test cases does not exceed $30$ .
2	19	Every query is of type `1`.
3	53	No additional constraints.

Samples

Input

Output

After all queries of the first test case, the maximum discomfort is $2$ . Both classroom $2$ on floor $1$ and classroom $1$ on floor $2$ have this value, so classroom $2$ on the lower floor is selected.