#P10029. Alice and Bob's Game of Subtraction

    ID: 12006 Type: Default 1000ms 256MiB

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