Game of Cards

Alice and Bob created a new game while at the beach this sum- mer. 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. In the figure, you can see an example with two piles and K = 1. The player to move might: a) Select the first pile and 0 cards to remove, being forced to remove 1 card from the top next. b) Select the second pile and 0 cards to remove, having to remove 1 card from the top next. c) 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. Luck- ily, this time Alice is first to play. Is Alice able to win this game? 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 Al- ice can win the game if she is the first to play. Input The input file contains several test cases, each of them as described below. 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 ≤ P ≤ 100 1 ≤ K ≤ 10 1 ≤ c ≤ 10 1≤N≤1000 Sizeofeachpile. Number of piles. Maximum number of cards a player can start to remove. Number on each card.

2/2 Output For each test case, a single string, stating ‘Alice can win.’ or ‘Bob will win.’, as appropriate. Notes: Explanation of output 1. The piles are the same, so Bob will always be able to mirror whatever move Alice makes. Explanation of output 2. 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 41 41111 6212121 41111 6212121 21 11 3121 22 532121 554321 Sample Output Bob will win. Alice can win. Alice can win.