만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

드래곤 슬레이어

면접 대비

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

요약
머리가 N개인 용을 두 검으로 베어 쓰러뜨릴 수 있는지, 그리고 왕자가 살아남을 수 있는지 판정합니다.
난이도

보통10점 중 5점

유형
BFS, 그래프, 시뮬레이션
정답자
아직 제출이 없습니다

문제

당신은 이런 이야기를 수없이 들어봤을 것이다. 아주 먼 곳, 아주 오래전에 착한 왕이 다스리던 왕국이 있었다. 왕에게는 아름다운 공주가 있었다. 어느 날 사악한 용이 공주를 납치했다. 다른 왕국의 왕자가 용을 죽이고 공주를 구하기로 결심했다. 싸움이 벌어졌고 용은 죽었으며 공주는 구출되었고 모두 행복하게 살았다.

이야기꾼들은 용과의 싸움이 실제로 어떤지 알지 못하기 때문에, 왕자가 무식한 힘, 뛰어난 검술, 영리한 꾀를 조합해 용을 죽이는 가짜 이야기를 지어낸다.

실제로 용을 죽이는 일은 순전히 수학 문제다. 용의 머리 개수는 가변적이지만 항상 0 이상이다. 용을 죽이는 유일한 방법은 머리 개수를 0으로 줄이는 것이다.

머리 개수는 마법의 검을 휘둘러야만 바뀐다. 각 마법의 검은 두 값 cc와 gg로 정해진다. 검을 한 번 휘두를 때마다 정확히 cc개의 머리를 베어야 한다. 그 뒤 용이 아직 살아 있다면(머리가 양수이면) 새로운 머리가 gg개 자란다.

머리가 cc개보다 적으면 검을 쓸 수 없다. 왕자에게도 머리가 하나 있다는 점에 유의하라. 따라서 왕자는 머리가 c−1c - 1개인 용을 죽일 수 있지만, 그렇게 하면 본인도 죽는다.

왕자는 마법의 검 두 자루를 찾았다. 하나는 c1c_1과 g1g_1, 다른 하나는 c2c_2와 g2g_2를 매개변수로 한다. 용의 머리는 NN개다. NN, c1c_1, g1g_1, c2c_2, g2g_2가 주어졌을 때, 왕자가 용을 죽일 수 있는지, 죽일 수 있다면 살아남을 수 있는지 판단하라.

입력

입력 파일의 첫 줄에는 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 NN, c1c_1, g1g_1, c2c_2, g2g_2가 주어진다.

출력

각 테스트 케이스마다 한 단어를 한 줄에 출력한다. 왕자가 싸움에서 이길 수 있으면(즉 용을 죽이고 살아남으면) PRINCE, 용을 죽일 수는 있지만 그 과정에서 왕자도 죽어야 하면 DRAW, 용을 죽일 수 없으면 DRAGON을 출력한다.

힌트

첫 번째 경우, 왕자는 첫 번째 검, 첫 번째 검, 두 번째 검 순서로 사용해 용을 죽일 수 있다.

두 번째 경우, 두 번째 검은 효과가 없다. 첫 번째 검을 쓰는 순간 왕자와 용이 모두 죽는다.

세 번째 경우, 왕자는 두 검 중 어느 것도 사용할 수 없다.

예제1

  1. 예제 1

    입력
    3
    
    20 7 1 8 5
    
    3 4 1 2 2
    
    100 102 0 103 0
    
    예상 출력
    PRINCE
    DRAW
    DRAGON