The knowledge of Grundy Number is required to solve this problem. We assume that you already know what it is. We will explain Grundy number at the bottom of this editorial. For more details, please search it on the Internet.

For a non-negative integer \(n\), let \(g(n)\) be the Grundy number of the state where there is only one pile containing \(n\) stones. In order to solve this problem, it is sufficient to find \(g(A_1), g(A_2), \ldots, g(A_N)\). Therefore, we will aim at enabling to find \(g(n)\) for any desired non-negative integer \(n\) with a proper precalculation.

For a non-negative integer \(n\), let us define \(h(n) := \max \lbrace g(0), g(1), \ldots, g(n) \rbrace\). Also, let \(\mathcal{S} := \lbrace 0, X_1, X_2, \ldots, X_M \rbrace\). Then, each of \(0, 1, 2, \ldots, h(n-1)-1, h(n-1)\) appears at least once in \(g(0), g(1), \ldots, g(n-1)\), so if \(n \not\in \mathcal{S}\), then it holds that

\[g(n) = \mathrm{mex}\lbrace g(0), g(1), \ldots, g(n-1) \rbrace = h(n-1) + 1,\]

\[h(n) = \max\lbrace h(n-1), g(n) \rbrace = h(n-1) + 1,\]

where \(\mathrm{mex}\) denotes the minimum non-negative integer not contained in the given set. Therefore, if \(n \not\in \mathcal{S}\), then

\[g(n) = h(n) = n - \bar{n} + h(\bar{n}), \tag{1}\]

where \(\bar{n}\) denotes the maximum element of \(\mathcal{S}\) less than or equal to \(n\). Once we could find \(g(n)\) and \(h(n)\) for all \(n \in \mathcal{S}\), we can use (1) to find \(g(n)\) for any desired non-negative integer \(n\) in an \(\mathrm{O}(\log M)\), so we will now explain how to find \(g(n)\) and \(h(n)\) for all \(n \in \mathcal{S}\).

For each element of \(\mathcal{S}\), let us find \(g(\cdot)\) and \(h(\cdot)\) in the ascending order of the element. Now let us fix \(n \in \mathcal{S}\), and supposing that \(g(n')\) and \(h(n')\) are already known for all \(n' \in \mathcal{S}\) less than \(n\), consider how to find \(n' \in \mathcal{S}\). (This is the situation where we may find any desired item of \(g(0), g(1), \ldots, g(n-1)\) and \(h(0), h(1), \ldots, h(n-1)\) in an \(\mathrm{O}(\log M)\) time using the values already obtained and (1).)

Let \(f_1, f_2, \ldots, f_K\) be the sequence of elements in the set \(\lbrace X_i - Y_i :i \in \lbrace 1, 2, \ldots, M \rbrace, X_i = n\rbrace\), that is, the set of the numbers of stones to which it is prohibited to transition from the state where there are \(n\) stones.

Then, \(g(n) = \mathrm{mex}\lbrace g(n') : n' \in \lbrace 0, 1, 2, \ldots, n-1 \rbrace \setminus \lbrace f_1, f_2, \ldots, f_K \rbrace \rbrace\), so if we can find the number of occurrences of each non-negative integer in

\[g(0), g(1), g(2), \ldots, g(n-1), \tag{2}\]

then we can find \(g(n)\) and \(h(n) = \max\lbrace h(n-1), g(n) \rbrace\) by checking if the number of occurrences of each non-negative integer in

\[g(f_1), g(f_2), \ldots, g(f_K)\]

is greater than or equal to the number of occurrences in (2). Therefore, it is sufficient to store the distribution of each non-negative integer (2) when finding \(\mathcal{S}\), and \(g(\cdot)\) and \(h(\cdot)\) for each element with associate arrays. The number of entries in the associate array can be enormous if all non-negative integers occurring at least once is recorded in the associative array, but, since all integers \(0, 1, 2, \ldots, h(n-1)\) appears at most once in (2), it is sufficient to record in the associative array those which occurs twice or more in (2), which bounds the number of entries in the associative array by \(O(M)\).

Therefore, this problem can be solved in a total of \(O(N+M\log M)\) time.

Bonus: About Grundy number

The game in this problem has the following properties:

• It is a impartial game (that is, the same set of moves is available for both players in every situation)
• The number of choices in each situation is finite
• It always finishes in a finite number of moves
• Regular (the player who is unable to make a move loses)

Here, we consider games with such property.

The Grundy number \(g(G)\) of the state \(G\) of a game is defined as follows.

Let \(\lbrace G_1, G_2, \ldots, G_n \rbrace\) be the set of states that can be transitioned from \(G\) by one move. We let \(g(G) := \mathrm{mex}\lbrace g(G_1), g(G_2), \ldots, g(G_n)\rbrace\). Here, \(\mathrm{mex}\) denotes the minimum non-negative integer that is not contained in the given set. If there are no states that can be transitioned from \(G\) by move, let \(g(G) := 0\).

In fact, from the state where the Grundy number is \(0\), the second player always wins; if it is positive, the first player always wins. Therefore, if we can calculate Grundy number of a state, we can determine which player has a winning strategy.

Here, let us define the addition of multiple games. The sum of \(n\) games \(G_1, G_2, \ldots, G_n\), denoted by \(G_1+G_2+\cdots +G_n\), is defined as follows.

From the \(n\) games \(G_1, G_2, \ldots, G_n\), each player chooses one of the \(n\) games and make a move on it in their turn. The player who is first to be unable to make a move on any of the \(n\) games loses.

The game in this problem can be regarded as the sum of \(N\) copies of “a game with only one pile.”

The following property of Grundy number is known: the Grundy number \(g(G_1+G_2+\cdots +G_n)\) of the sum game \(G_1+G_2+\cdots + G_n\) can be obtained as the bitwise exclusive logical sum of each component’s Grundy number \(g(G_1), g(G_2), \ldots, g(G_n)\); i.e. \(g(G_1+G_2+\cdots + G_n) =g(G_1) \oplus g(G_2) \oplus \cdots \oplus g(G_n)\).

Therefore, in this problem, once we found for each of the \(N\) piles the Grundy number of “the game consisting of only that pile,” the Grundy number of the entire game can be found as the exclusive logical sum of them; we can determine which player will win by checking if that is \(0\) or not.