34752번 - ZOAC 8

문제

2025년 11월, 제8회 ZOAC(Zero One Algorithm Contest)이 개최된다.

이 대회에는 참가 번호를 통해 참가자의 행운을 시험하고 수상하는 독특한 전통이 있다.

참가자는 각 문자가 0ドル$부터 9ドル$까지의 정수로 이루어진 길이가 10ドル$인 문자열을 참가 번호로 받으며, 참가 번호의 앞의 숫자 5ドル$개와 뒤의 숫자 5ドル$개로 나누어 두 개의 정수 $X$와 $Y$를 만든다. 두 정수 $X$와 $Y$ 사이의 범위 $(\min(X,Y) \le i \le \max(X,Y))$ 에 존재하는 소수 $i$의 개수를 행운 점수라고 한다.

재민이는 계산된 행운 점수를 바탕으로 다음과 같은 수상 규칙에 따라 수상자를 결정하려고 한다.

1. 행운상: 가장 높은 행운 점수를 얻은 참가자 중, 이름이 사전 순으로 가장 앞선 사람이 수상한다.
2. 불운상: 가장 낮은 행운 점수를 얻은 참가자 중, 이름이 사전 순으로 가장 앞선 사람이 수상한다.
3. 만약 최고점과 최저점이 같아 행운상과 불운상 수상자가 동일할 경우, 해당 참가자가 두 상을 모두 받는다.

$N$명의 참가자 정보가 주어질 때, 행운상과 불운상 수상자의 이름을 출력하는 프로그램을 작성해 보자.

입력

첫 번째 줄에 참가자의 수 $N$이 주어진다. $(2 \le N \le 100,000円)$

다음 $N$개의 줄에는 서로 다른 참가자의 이름과 고유한 10ドル$자리 참가 번호가 공백으로 구분되어 주어진다.

이름은 알파벳 대문자로 이루어진 길이가 1ドル$ 이상 20ドル$ 이하의 문자열이다.

참가 번호는 10ドル$자리의 숫자로 이루어진 문자열이며, 앞 5ドル$자리와 뒤 5ドル$자리는 각각 0ドル$으로 시작하지 않음이 보장된다.

출력

첫 번째 줄에 행운상을 받는 참가자의 이름을 출력한다.

두 번째 줄에 불운상을 받는 참가자의 이름을 출력한다.

만약 동점자가 여러 명일 경우, 사전 순으로 가장 앞선 참가자를 출력한다.

제한

노트

소수는 1ドル$보다 큰 양의 정수 중 1ドル$과 자기 자신만을 약수로 가지는 수를 의미한다. 특히, 1ドル$은 소수가 아님에 주의한다.