스마트 홈 상태 변경 점검

문제

스마트 홈 운영팀은 연결된 장치가 얼마나 자주 상태를 바꾸었는지 점검한다. 장치는 1번부터 D번까지 번호가 붙어 있고, 각 장치의 상태는 ON 또는 OFF 중 하나이다. 점검을 시작하기 직전에는 모든 장치가 OFF 상태이다. 운영 서버는 장치가 보내온 상태 보고를 받은 순서대로 로그에 저장한다. 로그 한 줄은 장치 번호, 세로줄 문자, 상태 문자열을 차례로 이어 붙인 형태이다. 예를 들어 3|ON은 3번 장치가 ON 상태라고 보고했다는 뜻이다. 장치 번호에는 불필요한 앞자리 0이 없으며, 상태 문자열은 대문자로만 주어진다. 로그 안에는 공백이 없다. 상태 보고를 받으면 해당 장치의 현재 상태를 보고된 상태로 갱신한다. 다만 현재 상태와 보고된 상태가 다를 때에만 그 장치의 상태 변경 횟수를 1 증가시킨다. 같은 상태가 연속해서 보고되면 뒤의 보고는 변경 횟수를 늘리지 않는다. 서로 다른 장치의 보고가 중간에 끼어 있어도 각 장치의 상태는 따로 유지한다. 운영팀은 모든 로그를 처리한 뒤 상태 변경 횟수가 많은 장치부터 점검하려 한다. 변경 횟수가 같으면 장치 번호가 작은 장치를 먼저 점검한다. 로그에 한 번도 등장하지 않은 장치도 점검 대상에 포함하며, 이러한 장치의 변경 횟수는 0이고 최종 상태는 OFF이다. 백엔드 담당자인 당신은 점검 순서의 앞에서 K개 장치를 뽑아 보고서를 만들어야 한다. 보고서에는 장치 번호, 상태 변경 횟수, 모든 로그를 처리한 직후의 상태를 함께 기록한다. 최종 상태가 OFF라는 이유로 점검 대상에서 제외하지 않는다. 로그 수가 0이어도 같은 정렬 규칙을 적용하며, 요청된 K개 장치를 모두 출력한다.

입력

첫째 줄에 장치 수 D, 로그 수 N, 보고할 장치 수 K가 공백으로 주어진다. 1 ≤ D ≤ 10,000, 0 ≤ N ≤ 20,000, 1 ≤ K ≤ D이다.
다음 N개 줄에는 각각 장치번호|상태 형식의 로그가 주어진다. 장치 번호는 1 이상 D 이하의 정수이고, 상태는 ON 또는 OFF이다. 각 줄에는 세로줄 문자가 정확히 하나 있으며 공백은 없다.
로그는 처리해야 하는 순서대로 주어진다.

출력

점검 순서의 앞에서 K개 장치를 한 줄에 하나씩 출력한다. 각 줄에는 장치 번호, 상태 변경 횟수, 최종 상태를 공백으로 구분하여 출력한다. 최종 상태는 ON 또는 OFF로 출력한다.

3 7 3
1|ON
1|ON
2|OFF
2|ON
1|OFF
3|ON
2|OFF

1 2 OFF
2 2 OFF
3 1 ON

4 0 2

1 0 OFF
2 0 OFF

3 4 2
3|ON
3|OFF
3|ON
1|OFF

3 3 ON
1 0 OFF

출처: Devin.KR 자체 제작