Hide

Problem G
Game of Cards

/problems/gameofcards/file/statement/en/img-0001.png

Alice and Bob created a new game while at the beach this summer. All they need is a set of numbered playing cards. They start by creating $P$ piles with all cards face-up and select a non-negative number $K$. After that, they take turns like this:

  1. A player starts by selecting one of the piles.

  2. Then, he removes from $0$ up to $K$ cards from the top of that pile, leaving at least one card in the pile.

  3. Next, he looks at the card left at the top of the pile and must remove a number of cards equal to its value (from the top of the same pile).

Whoever doesn’t have more cards to remove, or whoever is forced to remove more cards than those available on a pile, loses the game.

/problems/gameofcards/file/statement/en/img-0002.png
In the figure, you can see an example with two piles and $K = 1$. The player to move might:
  1. Select the first pile and $0$ cards to remove, being forced to remove $1$ card from the top next.

  2. Select the second pile and $0$ cards to remove, having to remove $1$ card from the top next.

  3. Select the second pile and $1$ card to remove, having to remove $2$ cards from the top next.

Alice has realized that Bob is very good at this game and will always win if he has the chance. Luckily, this time Alice is first to play. Is Alice able to win this game?

Task

Given the description of the piles with all the cards and the maximum number of cards they can start to remove, your goal is to find out whether Alice can win the game if she is the first to play.

Input

The first line contains $2$ space separated integers, $P$, the number of piles, and $K$, the maximum number of cards they can start to remove on their turn. The next $P$ lines start with an integer $N$, indicating the number of cards on a pile. $N$ space separated integers follow, representing the cards on that pile from the bottom to the top.

Constraints

$1 \leq P \leq 100$

Number of piles.

$1 \leq K \leq 10$

Maximum number of cards a player can start to remove.

$1 \leq c \leq 10$

Number on each card.

$1 \leq N \leq 1\, 000$

Size of each pile.

Output

A single string, stating “Alice can win.” or “Bob will win.”, as appropriate.

Sample Output Explanation

In the first sample, the piles are the same, so Bob will always be able to mirror whatever move Alice makes.

In the second sample, Alice can start by removing $0$ cards from the second pile and then $1$ card from its top. Two legal moves will be possible next, Bob will make one and Alice the other.

Sample Input 1 Sample Output 1
4 1
4 1 1 1 1
6 2 1 2 1 2 1
4 1 1 1 1
6 2 1 2 1 2 1
Bob will win.
Sample Input 2 Sample Output 2
2 1
1 1
3 1 2 1
Alice can win.
Sample Input 3 Sample Output 3
2 2
5 3 2 1 2 1
5 5 4 3 2 1
Alice can win.

Please log in to submit a solution to this problem

Log in