시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB95595367.089%

문제

한국항공대학교에는 올해 새로 들어온 큰 비행기가 있다.

항공대학교 본관 옆 A300 모형

올해 졸업식에 참가하는 모든 사람은 비행기가 보이게 사진을 찍고싶어하지만, 졸업식은 하루뿐이라 모든 사람이 원하는 장소와 시간에 촬영할 수 없다.

따라서 학교에서는 최대한 많은 사람이 촬영할 수 있도록 미리 졸업식 전날 원하는 장소와 시간대를 제출받아 예상되는 혼잡 장소와 시간대를 공지하기로 하였다.

제출은 다음과 같은 값을 가진다.

  • 학생 이름(name): 제출한 학생의 이름이다. 공백을 포함하지 않는 영어 소문자로 구성된 10자 이하의 한 단어로 구성된다. 만약 한 학생이 여러 번 제출한 경우, 가장 첫 번째 제출 이외의 제출들은 모두 무시한다.
  • 장소(place): 학생이 촬영하기를 원하는 장소이다. 공백을 포함하지 않는 영어 소문자로 구성된 20자 이하의 한 단어로 구성된다.
  • 시간대(time): 학생이 촬영하기를 원하는 시간대이다. 공백으로 구분된 두 개의 시각으로 주어지며, 시각은 $50,000$ 이하의 양의 정수로 주어진다. 첫 번째 시각은 촬영 시작 시각, 두 번째 시각은 촬영 종료 시각을 나타낸다. 단, 종료 시각이 시작 시각보다 항상 크다.

제출된 장소와 시간대의 목록을 이용해 학교가 혼잡 장소와 시간대를 공지하는 방법은 다음과 같다.

  1. 가장 많은 사람이 제출한 (장소, 시간대) 쌍을 선택한다.
  2. 만약 $1$번에 해당하는 구간이 여러 개라면, 사전 순으로 가장 앞에 오는 장소를 선택한다. 사전 순의 기준은 아스키 코드 순이다. 예를 들어 구간 배열 ['ab', 'a', 'aa', ba']를 정렬한 배열은 ['a', 'aa', 'ab', 'ba']가 된다.
  3. 만약 $2$번에서 고른 장소에 가장 많이 제출된 시간대가 여러 개라면, 가장 빠른 시간대를 고른다.

입력

첫째 줄에 제출 수 $N$이 주어진다. ($1 \le $ $N$ $ \le 100$)

다음 $N$개의 줄에 제출의 정보 name, place, time 가 한 줄에 하나씩 주어진다. 이때 빈 문자열은 입력으로 주어지지 않는다.

입력에서 주어지는 장소(place)의 종류는 최대 $10$가지이다.

출력

첫째 줄에 학교가 공지할 것으로 예상되는 혼잡 (장소, 시간대) 쌍을 공백으로 구분하여 출력한다. 이때 시간대는 조건을 만족하는 가장 긴 시간대를 의미한다.

예제 입력 1

8
suhwan cockpit 1 4
koosaga wing 3 5
youngjin elevator 4 7
suhwan aileron 1 10
minjae cockpit 2 6
dohun wing 2 5
range aileron 2 5
minchodan aileron 5 7

예제 출력 1

cockpit 2 4

예제 1번의 경우 다음과 같은 time table을 작성할 수 있다.


 

가장 많은 사람이 제출한 (장소, 시간대) 쌍은 cockpit의 (2, 4) 구간과 wing의 (3, 5) 구간 총 두 개가 있다. cockpit이 wing보다 사전순으로 앞에 오기 때문에 cockpit 장소의 (2, 4) 구간이 정답의 조건을 만족한다. 그 중 가장 긴 시간대를 만족하는 정답은 "cockpit 2 4"가 된다.

예제 입력 2

4
korea ab 1 6
aero a 1 2
space aa 1 4
univ ba 1 8

예제 출력 2

a 1 2

예제 입력 3

9
best dp 24409 28052
friend gop 14993 35460
strong gp 2790 21051
friend gop 35482 44328
strong dp 39442 40134
soldier gop 10825 40544
soldier dp 12059 13537
strong gp 48778 49362
udt gp 37117 40201

예제 출력 3

gop 14993 35460