학원 자습실의 마지막 현황

문제

한 학원에는 번호가 1부터 K까지 붙은 자습실이 있다. 학원은 학생 번호를 이용하여 자습실 이용 현황을 관리한다. 학생 번호는 1부터 1,000까지의 정수이며 같은 번호는 항상 같은 학생을 뜻한다. 업무를 시작할 때는 모든 자습실이 비어 있고, 어떤 학생도 자습실을 이용하고 있지 않다. 각 학생은 한 시점에 최대 하나의 자습실만 이용할 수 있다. 관리 기록에는 배정 기록과 퇴실 기록이 있다. 배정 기록은 학생 한 명과 자습실 하나를 지정한다. 해당 학생이 어느 자습실에도 없다면 지정한 자습실에 들어간다. 다른 자습실을 이용하고 있었다면 기존 자습실에서 나와 지정한 자습실로 이동한다. 이미 지정한 자습실에 있는 학생에게 같은 배정 기록이 다시 주어지면 현황은 바뀌지 않는다. 자습실의 수용 인원에는 제한이 없다. 퇴실 기록은 학생 한 명만 지정한다. 그 학생이 자습실을 이용하고 있다면 해당 자습실에서 나간다. 어느 자습실에도 없는 학생에게 퇴실 기록이 주어지면 아무 변화도 일어나지 않는다. 퇴실한 학생도 나중에 배정 기록을 받으면 다시 자습실에 들어갈 수 있다. 기록은 입력된 순서대로 하나씩 처리하며, 앞선 기록으로 바뀐 현황을 다음 기록에 반영한다. 학원은 모든 기록을 처리한 직후 가장 많은 학생이 남아 있는 자습실을 확인하려 한다. 가장 많은 학생 수가 같은 자습실이 여러 개라면 번호가 가장 작은 자습실을 선택한다. 중간에 학생이 가장 많았던 자습실이나 하루 동안 방문한 학생 수는 고려하지 않는다. 마지막에 모든 자습실이 비어 있다면 선택할 자습실이 없음을 나타내는 특별한 결과를 출력한다. 기록을 차례대로 반영하여 선택한 자습실 번호와 그곳에 남아 있는 학생 수를 구해야 한다.

입력

첫째 줄에 자습실 수 K와 기록 수 N이 공백으로 주어진다. K는 1 이상 100 이하, N은 0 이상 20,000 이하의 정수이다.
다음 N개 줄에 기록이 하나씩 주어진다.
배정 기록은 A U R 형식이며 학생 U를 자습실 R에 배정한다. 퇴실 기록은 L U 형식이며 학생 U를 퇴실 처리한다.
U와 R은 정수이며 1≤U≤1,000, 1≤R≤K이다.

출력

선택한 자습실 번호와 그 자습실에 남은 학생 수를 공백으로 구분하여 출력한다. 모든 자습실이 비어 있다면 0 0을 출력한다.

3 7
A 11 1
A 22 2
A 33 2
A 11 3
L 22
A 33 2
L 99

2 1

2 5
L 7
A 7 1
A 7 2
L 7
L 7

0 0

1 3
A 4 1
A 5 1
A 4 1

1 2

출처: Devin.KR 자체 제작