지금부터 서로 죽여라

시간 제한1초메모리 제한1024 MB

요약
나루토와 사스케가 번갈아 공격하거나 회복하며 싸울 때, 10^100번의 차례까지 승부가 나지 않으면 무승부인 게임의 결과를 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 수학, 구현
정답자
아직 제출이 없습니다

문제

나루토와 사스케는 서로를 죽이기 위한 혈투를 시작했다. 혈투가 시작되기 전, 나루토는 XX, 사스케는 YY의 체력을 가지고 있다. 혈투는 나루토와 사스케의 차례가 번갈아 가면서 진행된다. 차례는 나루토부터 시작되며, 각자 자신의 차례일 때 공격 또는 회복 중 하나를 선택하여 시행한다.

  • 공격을 선택하면 상대방의 체력이 자신의 공격력만큼 감소한다.
  • 회복을 선택하면 자신의 체력이 자신의 회복력만큼 증가한다.

회복을 선택한 경우, 최대 체력의 상한선은 존재하지 않는다. 즉, 초기의 체력을 넘어갈 수도 있다.

혈투가 진행되는 도중 나루토와 사스케 중 한 명의 체력이 00 이하가 되면, 그 순간 혈투가 종료되고 체력이 00 이하가 된 사람이 패배한다. 만약 1010010^{100}번의 차례가 진행된 이후에도 두 명의 체력이 모두 00보다 크다면, 무승부로 혈투가 종료된다.

나루토와 사스케는 혈투에서 이길 수 있다면 이기는 전략을 취하고, 이길 수 없다면 비기기 위해 최선을 다한다. 혈투의 정보가 주어질 때, 결과를 알아내 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. 이후 다음과 같은 형태의 입력이 TT개 주어진다. (1≤T≤103)(1\leq T \leq 10^{3})

각 테스트 케이스의 첫 번째 줄에 나루토의 체력 XX와 사스케의 체력 YY가 공백으로 구분되어 주어진다. (1≤X,Y≤1012)(1\leq X, Y \leq 10^{12})

각 테스트 케이스의 두 번째 줄에 나루토의 공격력 AA와 회복력 BB, 사스케의 공격력 CC와 회복력 DD가 공백으로 구분되어 주어진다. (1≤A,B,C,D≤1012)(1\leq A, B, C, D \leq 10^{12})

입력으로 주어지는 모든 수는 정수이다.

출력

각 테스트 케이스에 대해 나루토가 이긴다면 NARUTO, 사스케가 이긴다면 SASUKE, 둘이 비기게 된다면 DRAW를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    2
    10 20
    15 15 5 5
    10 20
    10 10 20 5
    
    예상 출력
    NARUTO
    SASUKE