Alice and Bob's Coin Flipping Game

Alice and Bob are playing a game with n coins numbered from \( 1 \) to \( n \). Each coin has two sides: heads and tails. Initially, some coins show heads and some show tails. The two players take turns flipping coins, and Alice moves first.

The rules for a move are as follows. A player must choose a coin numbered \( x \) which is currently tails up. Write \( x \) uniquely as \[ x = c \cdot 2^a \cdot 3^b, \] where \( a, b \) are nonnegative integers and \( c \) is a positive integer coprime with 2 and 3. Then the player has two options:

• Option 1 (power of 2): Choose integers \( p, q \) such that \( p \ge 1,\, 1\le q \le \text{MAXQ} \) and \( a \ge p\cdot q \). Then simultaneously flip every coin with number \[ c \cdot 2^{a-pj} \cdot 3^b \quad \text{for } j=0,1,2,\ldots,q. \]
• Option 2 (power of 3): Choose integers \( p, q \) such that \( p \ge 1,\, 1\le q \le \text{MAXQ} \) and \( b \ge p\cdot q \). Then simultaneously flip every coin with number \[ c \cdot 2^{a} \cdot 3^{b-pj} \quad \text{for } j=0,1,2,\ldots,q. \]

A coin flip changes the coin from heads to tails or vice‐versa. Note that if a coin is flipped more than once in a move, the flips cancel out pairwise (i.e. only an odd number of flips effectively changes its state).

The game ends when a player is unable to perform any move. Under perfect play, determine whether Alice (the first mover) can force a win.

inputFormat

The first line contains two integers \( n \) and \( \text{MAXQ} \) (the number of coins and the maximum value for \( q \) in a move).

The second line contains a string of length \( n \) consisting of characters 'H' and 'T'. The \( i \)-th character indicates the initial state of the coin with number \( i \) ('H' for heads and 'T' for tails).

outputFormat

Output a single line containing either "Alice" if the first player can force a win or "Bob" otherwise.

sample

1 1
T

Bob