현재 필요한 프로그램

문제

한 회사의 사내 IT 지원팀은 직원들이 사용하는 프로그램의 지원 수요를 관리한다. 직원과 프로그램에는 각각 양의 정수 번호가 부여되어 있다. 직원 한 명이 여러 프로그램의 지원을 요청할 수 있고, 같은 프로그램을 여러 직원이 요청할 수도 있다. 지원팀은 현재 지원이 필요한 직원과 프로그램의 쌍을 등록해 둔다. 기록을 처리하기 전에는 어떤 쌍도 등록되어 있지 않다. 이후 기록은 발생한 순서대로 주어지며, 등록 기록과 해제 기록의 두 종류가 있다. 등록 기록은 특정 직원이 특정 프로그램의 지원을 현재 필요로 한다는 뜻이다. 해제 기록은 해당 직원이 해당 프로그램의 지원을 더 이상 필요로 하지 않는다는 뜻이다. 등록 기록을 처리할 때 그 직원과 프로그램의 쌍이 아직 등록되어 있지 않으면 새로 등록한다. 이미 등록되어 있다면 아무 변화도 없다. 따라서 같은 등록 기록이 여러 번 들어와도 한 직원이 같은 프로그램의 수요에 여러 명으로 포함되지는 않는다. 해제 기록을 처리할 때는 해당 쌍이 등록되어 있으면 제거하고, 등록되어 있지 않으면 아무 변화도 주지 않는다. 한번 해제한 쌍도 뒤에 등록 기록이 나오면 다시 등록된다. 어떤 쌍을 등록하거나 해제하는 일은 같은 직원의 다른 프로그램이나 다른 직원의 등록 상태에 영향을 주지 않는다. 각 프로그램의 현재 수요는 모든 기록을 처리한 뒤 그 프로그램과 함께 등록되어 있는 서로 다른 직원의 수다. 지원팀은 현재 수요가 가장 큰 프로그램부터 안내 자료를 보강하려 한다. 모든 기록을 처리한 뒤, 현재 수요가 양수인 프로그램 중 수요가 가장 큰 프로그램의 번호와 그 수요를 구한다. 수요가 같은 프로그램이 여러 개라면 번호가 가장 작은 프로그램을 선택한다. 등록된 쌍이 하나도 남지 않았다면 선택할 프로그램이 없다는 뜻으로 번호와 수요를 모두 0으로 정한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 정수이며 0 ≤ N ≤ 40,000이다.
다음 N개 줄에 기록 종류 T, 직원 번호 U, 프로그램 번호 P가 공백으로 주어진다. T는 등록을 뜻하는 + 또는 해제를 뜻하는 -다. U와 P는 정수이며 각각 1 이상 100,000 이하이다.
기록은 처리해야 하는 순서대로 주어진다. 중복 등록이나 등록되지 않은 쌍의 해제도 입력될 수 있다.

출력

선택한 프로그램 번호와 해당 프로그램의 현재 수요를 공백으로 구분하여 한 줄에 출력한다. 등록된 쌍이 하나도 없으면 0 0을 출력한다.

8
+ 11 4
+ 12 4
+ 11 4
+ 11 7
- 12 4
+ 13 7
- 99 7
+ 14 4

4 2

5
+ 2 9
- 2 9
- 2 9
+ 2 9
- 2 9

0 0

4
+ 8 6
+ 8 3
+ 9 6
- 8 3

6 2

출처: Devin.KR 자체 제작