34979번 - 대신고와 쿼리

문제

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

대신고등학교 본관은 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ドル$번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

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

제한

노트