There is a strip 1 × n with two sides. Each square of the strip
(their total amount is 2n, n squares on each side) is painted in one
of two colors (let’s call them A and B). Alice and Bob play a game.
Alice makes the first turn. On each turn, a player can bend the strip in
half with the fold passing on the divisions of the squares (i.e. the turn
is possible only if the strip has an even length). Bending the strip can
be done either inwards or outwards. If the strip has become completely one
color after the next turn, then the winner is the player whose color is it
(A refers to Alice, B to Bob). If the current player has no legal
moves, but no one has won, the game ends with a draw.
Who will win if both players play optimally? This means that each player
tries to win; if it is not possible, to achieve a draw.
Input
The first line contains an integer n that is the length of the strip (1
≤ n ≤ 5 · 105).
The next two lines contain two strings of letters “A” and “B” with
lengths n, describing two sides of the strip. The letters that are under
each other, correspond to the different sides of the same square.
Output
If Alice wins, output “Alice”. If Bob wins, output “Bob”. If the game ends
with a draw, output “Draw”.
Samples
input | output |
---|
4
BBAA
BABB
| Bob
|
3
AAA
BBB
| Draw
|
2
AA
BB
| Alice
|
Notes
In the first example, Alice starts the game with the strip BBAA/BABB.
After her turn she can get the strip BB/AA or BB/AB. In both cases, Bob
can win by getting the strip B/B.
In the second example, Alice can’t make even the first turn, so the
result is a draw.
In the third example, Alice wins by the first move, getting the stripe A/A
from the strip AA/BB.
Problem Author: Nikita Sivukhin
Problem Source: Ural FU Junior Championship 2016