AT_arc219_d [ARC219D] Grid Game

There is an $ N \times N $ grid. The cell at the $ i $ -th row from the top and the $ j $ -th column from the left is denoted as cell $ (i,j) $ . Cell $ (i,j) $ initially contains $ A_{i,j} $ stones. Alice and Bob play the following game using this grid. - Starting with Alice, the two players alternate taking turns. - On each turn, the player chooses a cell and moves at least $ 1 $ and at most $ K $ stones from it together to an adjacent cell above or to the left. Specifically, the following steps are performed in order: 1. Choose a cell $ (i,j) $ that contains at least $ 1 $ stone. Cell $ (1,1) $ cannot be chosen. 2. Let $ c $ be the number of stones in cell $ (i,j) $ , and choose an integer $ x $ satisfying $ 1 \le x \le \min(c,K) $ . 3. Choose as the destination either cell $ (i-1,j) $ (if it exists) or cell $ (i,j-1) $ (if it exists), then remove $ x $ stones from cell $ (i,j) $ and move all of them to that cell. The player who cannot take a turn first loses. Determine which player wins when both play optimally. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ K $ $ A_{1,1} $ $ A_{1,2} $ $ \ldots $ $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ $ \ldots $ $ A_{2,N} $ $ \vdots $ $ A_{N,1} $ $ A_{N,2} $ $ \ldots $ $ A_{N,N} $

Output the answers for the test cases in order, separated by newlines. For each test case, output `Alice` if Alice wins when both play optimally, and `Bob` if Bob wins.

### Sample Explanation 1 Consider the first test case. For example, the game may proceed as follows (note that the players are not necessarily playing optimally): - Alice's turn: Choose cell $ (2,2) $ and remove $ 2 $ stones. Move the removed stones to cell $ (1,2) $ . - Bob's turn: Choose cell $ (1,2) $ and remove $ 2 $ stones. Move the removed stones to cell $ (1,1) $ . - Alice's turn: Choose cell $ (2,1) $ and remove $ 2 $ stones. Move the removed stones to cell $ (1,1) $ . - Bob's turn: Choose cell $ (2,1) $ and remove $ 1 $ stone. Move the removed stone to cell $ (1,1) $ . - Alice's turn: Choose cell $ (1,2) $ and remove $ 1 $ stone. Move the removed stone to cell $ (1,1) $ . - Bob's turn: Bob cannot take a turn and loses. By playing optimally, Alice can always beat Bob. Thus, output `Alice` on the first line. ### Constraints - $ 1\le T $ - $ 2\le N\le 100 $ - $ 1\le K\le 10^9 $ - $ 0\le A_{i,j}\le 10^9 $ - The sum of $ N^2 $ over all test cases is at most $ 3\times 10^5 $ . - All input values are integers.