시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 79 33 32 51.613%

문제

동현이와 현수와 승원이는 오랫동안 문제풀이 갓(god)의 칭호를 달기 위해 실력을 쌓아 왔다. 어느덧 세 명 모두 갓이라고 불리기에 손색 없는 실력이 되었으나, 하늘 아래 갓이 세 명일 수는 없는 법. 단 한 명의 진정한 갓을 어떻게 가릴지 논의하던 세 사람은 결국 이름에 을 붙였을 때 가장 잘 어울리는 사람을 진정한 갓으로 삼기로 결정했다.

그러나 어울린다는 것은 주관적이라서 여러 사람의 의견이 필요하다. 따라서 세 사람은 각자 자신의 친구들을 모아 투표를 진행하기로 했다. 이때 자기 자신이 후보에 들어 있으면 불공정한 투표가 될 수 있으므로, 각자 자기 자신은 후보에서 제외하고 투표를 진행했다. 투표가 끝나고 나면 각 사람은 다른 두 사람이 진행한 투표에서 자신이 받은 표를 가져가고, 이렇게 가져간 표가 가장 많은 사람이 진정한 갓이 된다. 만약 가장 많은 표를 받은 사람이 여러 명이라면 투표는 무효가 된다. 세 사람 모두 친구가 많기 때문에 각 투표에는 한 명 이상이 참가했음이 보장된다.

alt text

투표의 예시

오늘은 투표 결과가 공개되는 날이다. 그런데 세 사람은 서로를 견제하기 위해 전체 투표 결과를 내놓지 않고, 각자가 진행한 투표에서 두 후보가 받은 표의 비율만을 공개했다! 공개된 결과만 볼 때 동현이가 진정한 갓이 될 수 있을지 판단해 보자.

입력

첫 줄에 투표를 진행한 횟수를 의미하는 정수 T(1 ≤ T ≤ 100,000)가 주어진다.

다음 T개의 줄에 걸쳐 각 줄에 투표의 결과를 의미하는 6개의 정수 DH, DS, HD, HS, SD, SH(1 ≤ DH, DS, HD, HS, SD, SH ≤ 1,000)가 공백을 사이에 두고 주어진다.

  • DH, DS는 동현이가 진행한 투표에서 갓현수갓승원이 받은 표의 비율을 의미한다. 두 수는 서로소임이 보장된다.
  • HD, HS는 현수가 진행한 투표에서 갓동현갓승원이 받은 표의 비율을 의미한다. 두 수는 서로소임이 보장된다.
  • SD, SH는 승원이가 진행한 투표에서 갓동현갓현수가 받은 표의 비율을 의미한다. 두 수는 서로소임이 보장된다.

출력

T개의 줄에 걸쳐 각 줄에 각 투표에서 동현이가 진정한 갓이 될 수 있다면 GOD을, 불가능하다면 KDH를 출력한다.

예제 입력 1

3
3 2 3 2 2 1
2 3 1 2 1 3
1 1 2 3 1 2

예제 출력 1

GOD
KDH
GOD

노트

세 번째 예시에서는 다음과 같은 결과가 나오면 동현이가 진정한 갓이 될 수 있다.

alt text