#P10029. Alice and Bob's Game of Subtraction
Alice and Bob's Game of Subtraction
Alice and Bob's Game of Subtraction
Alice and Bob are playing a game with the following rules:
- Alice starts with an integer \(n\) and Bob starts with an integer \(m\).
- The players take turns, with Alice going first. On each turn, the active player performs an operation on the opponent's current integer \(h\) by subtracting \(h \bmod p\) from \(h\). That is, the new value of \(h\) becomes \[ h := h - (h \bmod p) = p \cdot \left\lfloor \frac{h}{p} \right\rfloor. \] Here, \(p\) is a given constant and \(\bmod\) denotes the modulus operation.
- The first player to make the opponent's number become \(0\) wins the game.
- If, after \(10^{10^{9961}}\) moves by each player, no one has won, the game is declared a draw.
Note that if the opponent's number is less than \(p\) (i.e. \(h<p\)), then \(h \bmod p = h\), and the operation will reduce the number to \(0\).
Your task is to determine the outcome of the game. Print "Alice" if Alice wins, "Bob" if Bob wins, or "Draw" if the game ends in a draw.
inputFormat
The input consists of a single line containing three integers \(n\), \(m\), and \(p\) separated by spaces. \(n\) is Alice's initial integer, \(m\) is Bob's initial integer, and \(p\) is the modulus constant.
It is guaranteed that \(n, m, p\) are positive integers.
outputFormat
Output a single line containing either "Alice", "Bob", or "Draw" indicating the result of the game.
sample
10 5 6
Alice