블록 게임

영희와 철수는 아래 그림처럼 나무로 된 블록을 쌓은 후, 차례를 바꿔가면서 블록을 선택하여 들어내는 게임을 한다. 자기 차례에는 블록을 반드시 하나 선택한 다음 들어내는데, 해당 블록을 들어낼 때 그 블록이 받치고 있는 모든 블록을 같이 들어내어야 한다. 좌우로 닿아 있는 블록 중 하나를 제거할 경우 옆의 블록에는 영향을 미치지 않는다.

예를 들어, 아래 그림같은 상황에서 블록 C를 들어낼 경우, D와 E도 같이 들어 낸다.

가장 하단에 있는 블록(위의 예에서 A)을 마지막에 들어내는 사람이 게임에 진다. 블록이 쌓인 정보가 주어진다. 게임을 하는 두 사람이 서로 최선을 다할 때, 게임을 먼저 시작하는 사람이 이기기 위해서는 첫 번째 차례에 어떤 블록을 선택하여야 하는지 구하는 프로그램을 작성하시오.

입력 형식

첫 번째 줄에 블록의 개수를 나타내는 정수 N($1 \le N \le 26$)이 주어진다.

다음 $N$개의 줄 각 줄에는 블록 하나의 정보를 나타내는 네 정수 $x_1$, $y_1$, $x_2$, $y_2$($0 \le x_1 < x_2 \le 1\,000$, $0 \le y_1 < y_2 \le 1\,000$)가 주어지며, 이는 왼쪽 아래 꼭짓점의 좌표가 $(x_1,y_1)$이고 오른쪽 위 꼭짓점의 좌표가 $(x_2,y_2)$인 블록이 존재한다는 뜻이다. 이 중 $i$번째 줄에 주어지는 블록은 $i$번째 알파벳 대문자로 나타낸다. 즉, 첫 번째 줄에 주어지는 블록은 A, 두 번째 줄에 줄어지는 블록은 B로... 나타내는 것이다.

블록은 서로 겹치지 않도록 입력이 주어지며, 블록 A의 $y_1 = 0$이고 나머지 블록의 아랫변은 어떤 다른 블록의 윗변과 닿아 있도록 입력이 주어진다. 또한, 게임을 시작하는 사람이 최선을 다 하면 반드시 이길 수 있는 입력만 주어진다.

출력 형식

게임을 먼저 시작하는 사람이 이기기 위해 첫 번째 차례에 선택할 수 있는 블록이 여러 개 있을 수 있다. 그런 블록을 모두 찾아 공백 구분 없이 출력한다. 알파벳 순서대로 출력할 필요는 없으나 같은 알파벳을 여러 번 출력해서는 안 된다.

예제

5
250 0 750 200
275 200 450 700
550 200 725 400
580 400 690 700
80 700 800 920

D

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 테스트케이스의 입력데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다. 또한 입력 케이스들 각각 점수가 다르다. 아래 그림은 각 테스트케이스를 나타내는 그림이며, 이 링크를 통해 모두 다운로드 가능하다.

해설