#389 Daeshin High School and Queries

Statement

대전대신고등학교 본관은 $4$ 개의 층으로 이루어져 있으며, 각 층에는 $N$ 개의 반이 있다. 층은 아래에서부터 $1$ 층, $2$ 층, $3$ 층, $4$ 층이고, 각 층의 반은 왼쪽부터 $1$ 반, $2$ 반, $\cdots$ , $N$ 반이다.

처음에는 모든 반의 불쾌함이 $0$ 이다. 다음 두 종류의 쿼리를 처리하여라.

1 $a$ $b$ : $a$ 층 $b$ 반에서 공사가 발생한다. $a$ 층 $b$ 반과 상하좌우로 인접한 반의 불쾌함이 각각 $1$ 증가한다. 건물 밖에 해당하는 위치는 무시한다.
2 $a$ : $a$ 층에서 불쾌함이 가장 높은 반의 번호를 출력한다. 그러한 반이 여러 개라면 번호가 가장 작은 반을 출력한다.

모든 쿼리를 처리한 뒤, 건물 전체에서 불쾌함이 가장 높은 반을 이달의 오량반으로 선정한다. 그러한 반이 여러 개라면 층수가 가장 작은 반을 선택하고, 층수도 같다면 반 번호가 가장 작은 반을 선택한다.

각 2번 쿼리의 답과 이달의 오량반을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 쿼리는 다음 중 하나의 형식으로 주어진다.

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

각 테스트 케이스의 2번 쿼리에 대해, 조건을 만족하는 반의 번호를 한 줄에 하나씩 출력한다.

각 테스트 케이스의 모든 쿼리를 처리한 뒤, 이달의 오량반의 층수와 반 번호를 공백으로 구분하여 한 줄에 출력한다.

#	Score	Constraints
1	28	모든 테스트 케이스에 대한 $N$ 의 합은 $30$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 $30$ 이하이다.
2	19	모든 쿼리의 종류는 `1`이다.
3	53	추가적인 제약이 없다.

Input

Output

첫 번째 테스트 케이스에서 모든 쿼리를 처리한 뒤 불쾌함의 최댓값은 $2$ 이다. $1$ 층 $2$ 반과 $2$ 층 $1$ 반이 이 값을 가지므로 층수가 더 작은 $1$ 층 $2$ 반이 선택된다.