Nullify The Matrix
Contest: Codeforces Round 685 (Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, games

Jeel and Ashish play a game on an $$$n \times m$$$ matrix. The rows are numbered $$$1$$$ to $$$n$$$ from top to bottom and the columns are numbered $$$1$$$ to $$$m$$$ from left to right. They play turn by turn. Ashish goes first.

Initially, each cell of the matrix contains a non-negative integer. Each turn, a player must perform all of the following actions in order.

- Choose a starting cell $$$(r_1, c_1)$$$ with non-zero value.
- Choose a finishing cell $$$(r_2, c_2)$$$ such that $$$r_1 \leq r_2$$$ and $$$c_1 \leq c_2$$$.
- Decrease the value of the starting cell by some positive non-zero integer.
- Pick any of the shortest paths between the two cells and either increase, decrease or leave the values of cells on this path unchanged. Note that:   a shortest path is one that passes through the least number of cells;  all cells on this path excluding the starting cell, but the finishing cell may be modified;  the resulting value of each cell must be a non-negative integer;  the cells are modified independently and not necessarily by the same value.

If the starting and ending cells are the same, then as per the rules, the value of the cell is decreased. No other operations are performed.

The game ends when all the values become zero. The player who is unable to make a move loses. It can be shown that the game will end in a finite number of moves if both players play optimally.

Given the initial matrix, if both players play optimally, can you predict who will win?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — the dimensions of the matrix.

The next $$$n$$$ lines contain $$$m$$$ space separated integers $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 10^6$$$) — the values of each cell of the matrix.

Output format:
For each test case, if Ashish wins the game, print "Ashish", otherwise print "Jeel" (without the quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only cell of the matrix is 0. There are no moves Ashish can make. Jeel is the winner.

In the second test case, Ashish can choose $$$(r_1, c_1) = (r_2, c_2) = (1,3)$$$ and reduce the cell to $$$0$$$, leaving $$$[0, 0, 0]$$$. Jeel cannot perform any moves. Ashish wins.

Example input:
4
1 1
0
1 3
0 0 5
2 2
0 1
1 0
3 3
1 2 3
4 5 6
7 8 9

Example output:
Jeel
Ashish
Jeel
Ashish

Editorial:
Let's consider diagonals $$$d$$$ of the form $$$r+c$$$ - the diagonals where the sum of row index $$$(r)$$$ and column index $$$(c)$$$ is constant. Then xor of a diagonal $$$d$$$ will be $$$xor(d) = a(r_1,c_1)\oplus a(r_2,c_2)\oplus...a(r_n,c_n)$$$, such that $$$r_1 + c_1 = d$$$, $$$r_2 + c_2 = d$$$, .... $$$r_n + c_n = d$$$.
$$$Solution:$$$ If $$$\forall d,\hspace{0.1cm}xor(d) = 0$$$ at the start of the game, then Jeel wins. Else, Ashish wins.
$$$Proof:$$$
Let's define two states $$$S$$$ and $$$S'$$$:
$$$S$$$ : $$$\forall d,\hspace{0.1cm}xor(d) = 0$$$
$$$S'$$$ : $$$\exists d,\hspace{0.1cm}xor(d) \ne 0$$$
$$$Lemma\hspace{0.1cm}1:$$$ Any move on $$$S$$$ converts the matrix to $$$S'$$$.
$$$Proof:$$$ If we are in state $$$S$$$, $$$xor(r1 + c1)=0$$$. Since, we need to anyhow decrease value of $$$(r1, c1)$$$, $$$xor(r1 + c1)$$$ will become non-zero. Hence, any move on $$$S$$$ converts the matrix to $$$S'$$$.
$$$Lemma\hspace{0.1cm}2:$$$ There always exists a move on $$$S'$$$ to convert it to $$$S$$$.
$$$Proof:$$$ If we are given an $$$S'$$$ state, we can convert it into $$$S$$$ as follows: Note that the diagonals between $$$(r1 + c1)$$$ and $$$(r2 + c2)$$$ can be arbitrarily changed to any value. $$$(r1, c1)$$$ can only be decreased in value. Let $$$(r1 + c1)$$$ be such a diagonal that there is no diagonal $$$d < r1 + c1$$$ with $$$xor(d) != 0$$$. Also, in order to ensure that we can make $$$xor(r1 + c1) = 0$$$ by decreasing, we select such a cell $$$(r1, c1)$$$ whose largest set bit is equal to the largest set bit of $$$xor(r1 + c1)$$$. In this way, we ensure that diagonal $$$r1 + c1$$$ can be made $$$0$$$. Now, we need to fix $$$(r2, c2)$$$. Let's fix $$$(r2, c2)$$$ such that there is no diagonal $$$d > r2 + c2$$$, such that $$$xor(d) != 0$$$. Since, (r2, c2) can be increased as well as decreased, we can easily make $$$xor(r2 + c2) = 0$$$. The diagonals in between can be arbitarily changed, so making them $$$0$$$ is trivial. At the end of this move, all diagonals have become $$$0$$$. Hence, given a state $$$S'$$$, we can always convert it to $$$S$$$.
Due to $$$Lemma\hspace{0.1cm}1$$$ and $$$Lemma\hspace{0.1cm}2$$$, a person starting on state $$$S'$$$ can always stay at $$$S'$$$ and can always force the opponent to start on state $$$S$$$. Since the state at the end of the game will be $$$S$$$, the opponent will always lose.
Complexity: $$$O(n * m)$$$