Daeshin High School and Queries

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 $a$. 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.

The input is given in the following format.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

Each case is given in the following format.

$N\ Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

Each query has one of the following forms.

$1\ a\ b$ $2\ a$

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.

• $1 \leq T \leq 1\,000$.
• $1 \leq N \leq 1\,000$.
• $1 \leq Q \leq 1\,000$.
• In a type 1 query, $1 \leq a \leq 4$ and $1 \leq b \leq N$.
• In a type 2 query, $1 \leq a \leq 4$.
• The sum of $N$ over all test cases does not exceed $1\,000$.
• The sum of $Q$ over all test cases does not exceed $1\,000$.