열어 둔 대화방

문제

한 회사의 사내 메신저에는 1번부터 K번까지 번호가 붙은 대화방이 있다. 한 직원의 메신저는 한 번에 대화방 하나만 화면에 열어 둘 수 있으며, 아무 대화방도 열지 않은 상태로 둘 수도 있다. 처음에는 아무 대화방도 열려 있지 않고, 모든 대화방의 읽지 않은 메시지 수는 0이다. 메신저의 동작 기록에는 세 종류의 사건이 시간순으로 남아 있다. 사건 `1 c`는 c번 대화방에 새 메시지 한 개가 도착했다는 뜻이다. 이때 c번 대화방이 화면에 열려 있다면 직원이 메시지를 즉시 읽으므로 읽지 않은 메시지 수는 늘지 않는다. 그 외의 경우에는 c번 대화방의 읽지 않은 메시지 수가 1 늘어난다. 새 메시지가 도착해도 화면에 열려 있는 대화방은 바뀌지 않는다. 사건 `2 c`는 직원이 c번 대화방을 화면에 여는 동작이다. 이전에 다른 대화방이 열려 있었다면 그 대화방을 닫고 c번 대화방을 연다. 이 동작으로 c번 대화방의 기존 메시지를 모두 읽으므로 해당 방의 읽지 않은 메시지 수는 0이 된다. 이미 열려 있는 대화방을 다시 여는 사건도 주어질 수 있으며, 같은 규칙을 적용한다. 다른 대화방의 읽지 않은 메시지 수는 바뀌지 않는다. 사건 `3`은 화면에 열려 있는 대화방을 닫는 동작이다. 이후에는 아무 대화방도 열려 있지 않다. 이미 아무 대화방도 열려 있지 않아도 이 사건은 정상적으로 처리하며, 읽지 않은 메시지 수에는 영향을 주지 않는다. 모든 사건을 처리한 뒤 전체 대화방에 남은 읽지 않은 메시지 수의 합과, 읽지 않은 메시지가 가장 많은 대화방의 번호를 구한다. 가장 많은 방이 여러 개라면 번호가 가장 작은 방을 선택한다. 모든 방의 읽지 않은 메시지 수가 0이라면 선택할 방의 번호를 0으로 정한다.

입력

첫째 줄에 대화방의 수 K와 사건의 수 N이 공백으로 구분되어 주어진다. K는 1 이상 1,000 이하의 정수이고, N은 1 이상 40,000 이하의 정수다.
다음 N개 줄에 사건이 하나씩 주어진다. 각 사건은 `1 c`, `2 c`, `3` 중 하나다. c는 1 이상 K 이하의 정수다. 사건은 입력 순서대로 처리한다.

출력

첫째 줄에 모든 사건을 처리한 뒤 읽지 않은 메시지 수의 합을 출력한다. 둘째 줄에 읽지 않은 메시지가 가장 많은 대화방의 번호를 출력한다. 동점이면 가장 작은 번호를 출력하고, 모든 방이 0개이면 0을 출력한다.

3 10
1 2
1 1
2 2
1 2
1 3
3
1 2
1 3
2 1
1 1

3
3

4 5
1 4
1 2
1 2
1 4
3

4
2

1 4
1 1
2 1
1 1
3

0
0

출처: Devin.KR 자체 제작