Dragon Slayer

Interview

Time limit1sMemory limit1024 MB

Summary

Given a dragon with N heads and two swords (c, g), decide whether the prince can kill it and survive, can only kill it while dying (DRAW), or cannot kill it.

Level: Medium5 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Statement

You have probably heard this story a thousand times. Long ago and far away, a good king ruled a kingdom, and he had a beautiful daughter. One day an evil dragon abducted the princess. A prince from another kingdom decided to kill the dragon and rescue her. There was a fight, the dragon died, the princess was saved, and everyone lived happily ever after.

Storytellers have no idea what a fight with a dragon actually looks like, so they invent tales in which the prince combines brute force, expert swordsmanship, and clever tricks.

In reality, killing a dragon is a purely mathematical problem. The dragon has a variable number of heads, always non-negative. The only way to kill it is to reduce its heads to zero.

Heads change only when someone swings a magic sword. Each sword is described by two parameters, $c$ and $g$ . Each swing must cut off exactly $c$ heads. Afterwards, if the dragon is still alive (it has a positive number of heads), it grows $g$ new heads.

A sword cannot be swung if there are fewer than $c$ heads to cut. The prince also has a head. He can kill a dragon with exactly $c - 1$ heads, but he dies doing so.

The prince found two magic swords: one with parameters $c_1$ and $g_1$ , and the other with $c_2$ and $g_2$ . The dragon has $N$ heads. Given $N$ , $c_1$ , $g_1$ , $c_2$ , and $g_2$ , determine whether the prince can kill the dragon, and if so, whether he can survive.

Input

The first line contains an integer $T$ , the number of test cases. Each test case is preceded by a blank line.

Each test case is one line containing the numbers $N$ , $c_1$ , $g_1$ , $c_2$ , and $g_2$ .

Output

For each test case, print one word on a line: PRINCE if the prince can win the fight (kill the dragon and survive), DRAW if he can kill the dragon but must die to do so, or DRAGON if the dragon cannot be killed.

Hint

In the first case, the prince can kill the dragon by using the swords in the order first, first, second.

In the second case, the second sword has no effect. As soon as the prince uses the first sword, both he and the dragon die.

In the third case, the prince cannot use either sword.

Examples1

Example 1

Input

3

20 7 1 8 5

3 4 1 2 2

100 102 0 103 0

Expected output

PRINCE
DRAW
DRAGON