시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB23212812456.109%

문제

"너무 시끄러워서 잠을 잘 수가 없어!" (물론 학교에선 자면 안 됩니다.)

대신고등학교 본관은 $4$층으로 구성되어 있으며, 각 층마다 $N$개의 반이 있다. 반의 번호는 왼쪽부터 오른쪽으로 $1$번부터 $N$번까지 매겨지고, $1$층부터 $4$층까지는 아래에서 위로 올라간다. 따라서 $1$층 $1$반은 건물의 가장 아래층, 가장 왼쪽에 있는 반이다.

현재 대신고의 본관은 공사 중이다. 이 공사 소리는 한 반에서 공사를 할 경우, 그 반 및 같은 층의 바로 왼쪽과 오른쪽 반, 바로 아래층과 위층의 같은 반에 영향을 미친다. 단, 존재하지 않는 반은 무시된다. 예를 들어 $1$층이면 아래층이 없고, $1$반이면 그 왼쪽 반이 없으며, $N$반이면 그 오른쪽 반이 없다.

처음에는 모든 반의 불쾌함이 $0$이며, 총 $Q$개의 쿼리가 주어진다. 각 쿼리는 다음 두 가지 중 하나로 입력된다:

  • $1$ $a$ $b$: $a$층 $b$반에서 공사가 발생한다. 이때 영향을 받는 모든 반의 불쾌함을 $1$만큼 증가시킨다. 같은 위치에서 공사가 여러 번 발생하면 그때마다 불쾌함이 증가한다.
  • $2$ $a$: $a$층에서 지금까지 불쾌함이 가장 높은 반의 번호를 출력한다. $a$층에서 불쾌함이 가장 높은 반이 둘 이상인 경우 반 번호가 더 작은 반을 출력한다.

또한 모든 쿼리를 수행한 후, 건물 전체에서 불쾌함이 가장 높은 반을 이달의 오량반으로 선정한다. 불쾌함이 가장 높은 반이 여러 반인 경우, 층수가 더 낮은 층을 우선으로 하고, 층수까지 같다면 반 번호가 더 작은 반을 선택한다.

모든 쿼리를 수행한 뒤, 이달의 오량반의 층수와 반 번호를 공백으로 구분하여 한 줄에 출력하는 프로그램을 작성하자!

입력

첫번째 줄에 반의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 1\,000)$

두번째 줄부터 $Q$번에 걸쳐 위에서 설명한 것과 같은 쿼리가 주어진다. $(1 \le a \le 4$; $1 \le b \le N)$

출력

$2$번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

모든 쿼리를 수행한 뒤, 마지막 줄에 이달의 오량반의 층수와 반 번호를 공백으로 구분하여 한 줄에 출력한다.

예제 입력 1

4 5
1 1 2
1 2 3
1 3 1
2 2
2 3

예제 출력 1

2
1
1 3

예제 입력 2

6 4
1 2 4
1 3 3
1 4 5
2 3

예제 출력 2

4
2 3