Limits 1s, 256 MB

Mita’s team had always been a good team when it came to competitive programming, and this year, their hard work and dedication had finally paid off. They got selected for the ICPC regional competition. It was a momentous occasion, and they knew they had to give it their all to succeed.

In preparation for the upcoming ICPC regional competition, Mita’s team decided to engage in friendly practice sessions. In one practice contest, they found an interesting problem about two players passing through two paths having obstacles.

The problem statement is as follows:

Two paths having N(1toN)N \: (1 \: to \: N) points are given for players AA and BB. Both players will start traveling at the same time from point 11. These paths contain obstacles at different points. If any player encounters an obstacle at an even-numbered point, they must move back 11 step, while encountering an obstacle at an odd-numbered point requires them to move back 22 steps. Once a player encounters an obstacle, it becomes inactive and will not impact that player’s move again. Traveling to every point requires 11 second.

The player who reaches point NN before another player will win the game. If both players reach point N at the same time, the game is considered a tie.

As you are one of the teammates, help your teammates determine who will win the game or whether the game will be tied.

It is guaranteed that there are no obstacles at points 11 and NN.

Input

The first line provides a single integer NN, which represents the number of points on two paths. The second line consists of two integers,  XX and YY. These indicate the number of obstacles on the paths for players AA and BB respectively. The third line contains XX integers, a1,a2,,axa_1,a_2,…,a_x, representing the positions of obstacles on player AsA’s path. The fourth line contains YY integers, b1,b2,,byb_1,b_2,…,b_y, representing the positions of obstacles on player BsB’s path.

3N1053 \leq N \leq 10^5

0X,YN20 \leq X, Y \leq N-2

1<ai<N1 < a_i < N

1<bi<N1 < b_i < N

Output

For each test case print A“A” without quote if player AA wins the game, or print B“B” without quote if player BB wins the game, or print DRAW“DRAW” without quote if the game is tied.

Samples

InputOutput
10
2 4
2 4
2 5 6 9
A

For the first test case, let's simulate the moves for player AA:

  • Player AA starts at point 1.

  • Player AA reaches point 2 in 1 second.

  • Player AA encounters an obstacle at point 2 and moves back one step to point 1 in 1 second.

  • Player AA reaches point 2 (again) in 1 second.

  • Player AA reaches point 3 in 1 second.

  • Player AA reaches point 4 in 1 second.

  • Player AA encounters an obstacle at point 4 and moves back one step to point 3 in 1 second.

  • Player AA reaches point 4 (again) in 1 second.

From this point on, player AsA’s path has no obstacles. Player AA reaches point 10 in a total of 13 seconds.

In the same way, Player BB reaches point 10 in a total of 21 seconds.

Since, player AA reaches point 10 before player BB, therefore, the output is "A""A" because Player AA wins the game.

InputOutput
10
4 2
2 5 6 9
2 4
B
InputOutput
10
4 4
2 5 6 9
2 5 6 9
DRAW

Be careful about the newline(‘\n’) at the end.

Submit

Login to submit.

Statistics

72% Solution Ratio
Reyad.1935Earliest, 5M ago
Tahmidul.4404Fastest, 0.0s
Tahmidul.4404Lightest, 5.1 MB
faheeedShortest, 492B
Toph uses cookies. By continuing you agree to our Cookie Policy.