Hyper Smawk Bros

Let the real state be $(n,l)$:

• $n$ is the current health.
• $l$ is the forbidden damage from the opponent's previous move.
• $l=0$ means no damage is forbidden, which is the initial state.

A move chooses $x\in[1,m]$, $x\ne l$, and either kills immediately if $x\ge n$, or sends the game to $(n-x,x)$.

Call a state losing if the player to move loses. Define:

$$\text{$n$ is evil} \iff (n,0)\text{ is losing.}$$

The answer is NO exactly for evil $n$.

Why each health has only three possible types

For a fixed health $n$, look at the set $G(n)$ of winning damages if they are legal. A damage $x$ is in $G(n)$ if it kills immediately, or if it moves to a losing state $(n-x,x)$.

Now consider $(n,l)$. This state is losing exactly when all winning damages are banned. But only one damage is banned.

So:

• If $G(n)$ is empty, then every $(n,l)$ is losing. This is an evil health.
• If $G(n)=\{a\}$, then only $(n,a)$ is losing. This is a neutral health.
• If $|G(n)|\ge2$, then no single ban can stop all winning moves. This is a good health.

That is the big compression. We never need a full table of size $n\cdot m$.

Evil values are sparse

Suppose $a<b$ are both evil and $b-a\le m$. From $(b,0)$, the current player can subtract $b-a$ and move to health $a$. Since $a$ is evil, $(a,b-a)$ is losing too, so this would be a winning move. Contradiction.

Therefore consecutive evil values differ by at least $m+1$.

Even $m$

If $m$ is even, then $m+1$ is odd. The evil values are exactly multiples of $m+1$.

From a multiple of $m+1$, if the first player subtracts $x$, Bob subtracts

$$m+1-x.$$

This is always in $[1,m]$, and because $m+1$ is odd, it is never equal to $x$. So Bob's reply is legal. Every pair of moves removes exactly $m+1$ health, and Bob gets the final hit.

If $n$ is not a multiple of $m+1$, the first player moves down to the previous multiple and wins.

So for even $m$:

$$\boxed{n\text{ is evil} \iff n\equiv 0\pmod{m+1}}.$$

Odd $m$

Now $m+1$ is even, and the mirror reply breaks at the middle move:

$$h=\frac{m+1}{2}.$$

If the opponent plays $h$, replying with $h$ is illegal. That one annoying move is the whole reason this is not a baby modulo problem.

Let the evil values for this fixed odd $m$ be

$$v_0=0<v_1<v_2<\cdots.$$

We use $v_0=0$ as a fake boundary value. The first real evil value is always $m+1$.

From an evil value $v_k$, every health

$$v_k+1, v_k+2, \ldots, v_k+m$$

is not evil, because the current player can move directly back to $v_k$ unless exactly that move is forbidden.

So the next evil value is at least $v_k+m+1$.

A structural argument shows it is never later than $v_k+m+2$. In short: if $v_k+m+1$ is not evil, the only way that can happen is a special neutral state exactly halfway back through the broken middle move. That special event cannot also save $v_k+m+2$, so one of these two positions is evil.

Thus:

$$\boxed{v_{k+1}\in\{v_k+m+1,\ v_k+m+2\}}.$$

So we only need to decide whether $v_k+m+1$ is evil.

The recursive check

Define win(n, j) as follows:

• $v_j$ is the nearest known evil value below $n$.
• The direct move $n-v_j$ is unavailable or forbidden.
• The function returns whether the current player can still force a win.

The structural lemmas reduce all possible useful moves to at most three cases.

1. Two-step finish through $v_j-1$.

Depending on whether the previous evil gap was $m+1$ or $m+2$, there is one direct tactical move that reaches $v_j-1$ and guarantees control of the game. This is the constant-time condition in the code.

2. Block the move to $v_j$.

If $n-v_j$ is even, play

$$x=\frac{n-v_j}{2}.$$

Then the opponent is at health $n-x$, and their direct move to $v_j$ is also $x$, which is now forbidden. So the opponent's state is exactly another win check. If the opponent cannot win there, this move wins.

3. Block the move to $v_{j-1}$.

Similarly, if $n-v_{j-1}$ is even and half of it is at most $m$, play

$$x=\frac{n-v_{j-1}}{2}.$$

This blocks the opponent's direct move to the previous evil value, so recurse with index $j-1$.

If none of these works, the state is losing under the blocked-direct-move condition.

Now generation is simple:

• Start with evil values $0$ and $m+1$.
• Let the last evil value be now.
• Test now + m + 1 with win.
• If it is winning, the next evil is now + m + 2.
• Otherwise, the next evil is now + m + 1.

Because evil values are spaced by about $m$, for one fixed $m$ we generate only $O(N/m)$ values. Across all queried odd $m$, this totals about

$$O\left(N\log N\right)$$

for $N=10^6$, which is fine.

Algorithm

For each test case:

• If $m$ is even, answer with n % (m+1).
• If $m$ is odd, process that $m$ once, generating evil values up to the largest queried $n$ for that $m$.
• A query is NO iff its $n$ appears in the evil list.

The constraints pretend this wants a giant DP. It does not. The game is mostly sparse bad positions plus one cursed middle move.