Bug Is Feature (Unconditional Version)

Reduce One Game

Sort the current triple as $(p, p+d, p+2d)$. The labels $a,b,c$ are not sacred after a move; if you treat them like permanent names, the problem starts lying to you. Sort after every move.

Now classify what can happen when one number is increased.

• Increasing the largest is impossible. The two smaller numbers already force the third AP element to be the old largest.
• Increasing the middle keeps $p$ and $p+2d$. The only larger value that works is $p+4d$, giving $(p, p+2d, p+4d)$, so the new difference is $2d$. This needs $p+4d \le x$.
• Increasing the smallest has two options. It can become the new middle, which forces value $p+3d/2$, possible only when $d$ is even. Then the state becomes $(p+d, p+3d/2, p+2d)$ with difference $d/2$. Or it can become the new largest, value $p+3d$, giving $(p+d, p+2d, p+3d)$ with the same difference $d$.

Let

$t = x-(p+2d)$

be the slack above the current largest element. The start position $p$ disappears from the game. Nice. A state is determined by $(d,t)$, and the moves are:

• if $d$ is even: $(d,t) -> (d/2,t)$;
• if $t \ge d$: $(d,t) -> (d,t-d)$;
• if $t \ge 2d$: $(d,t) -> (2d,t-2d)$.

Let $g(d,t)$ be the Grundy value.

Strip The Odd Part

Write

$d=m2^k$

where $m$ is odd. Also write $t=ms+q$ with $0 \le q<m$.

Every threshold and subtraction is a multiple of the current difference, hence a multiple of $m$. The remainder $q$ never affects which moves exist and never changes. So the Grundy value only depends on $k$ and $s$:

$g(d,t)=F(k,s)$.

The recurrence is

$F(k,s)=mex($ legal options $)$, where the options are:

• $F(k-1,s)$ if $k>0$;
• $F(k,s-2^k)$ if $s \ge 2^k$;
• $F(k+1,s-2^{k+1})$ if $s \ge 2^{k+1}$.

For $k=0$, this gives $F(0,s)=s \bmod 2$: odd slack-blocks win, even ones lose.

The Periodic Word

Define a word $W_k$ of length $2^{k+1}$, where $W_k[s] = F(k,s)$ inside one period.

Base:

$W_0 = [0,1]$.

For $k>0$, build $W_k$ from $W_{k-1}$:

• lower half: apply map $A$, where $A(0)=1$ and $A(1)=A(2)=0$;
• upper half: apply map $B$, where $B(0)=B(1)=2$ and $B(2)=1$.

Why? In the lower half $s<2^k$, the same-diff and double-diff moves are not initially available, so the only important move is to $F(k-1,s)$. The mex of one value is exactly map $A$.

In the upper half, write $s=2^k+u$. The halve move gives $F(k-1,u)$ and the same-diff move gives the lower-half value $A(F(k-1,u))$. The mex of those two values is exactly map $B$.

For later periods, the wrapped same-diff move and the double-diff move show up, but they do not change the mex. This is just a tiny three-value check over $0,1,2$: the extra values are never equal to the candidate mex. So $F(k,s)$ really is periodic with period $2^{k+1}$, and the construction above is valid.

That means a single Grundy value can be computed by reading the low $k+1$ bits of $s$: start from $W_0[s \bmod 2]$, then apply $A$ or $B$ depending on each next bit.

XOR Over A Huge Range

For one series, $x$ runs from $l$ to $r$. Since the initial largest is $c$, the slack is

$t=x-c.

Let the initial difference be $d=b-a=m2^k$.

All $t$ with the same $s=\lfloor t/m \rfloor$ have the same Grundy value. Since $m$ is odd, every complete block contributes one copy of that value to the XOR.

For prefix $t=0..T$:

• $S=\lfloor T/m \rfloor$ complete earlier blocks are $s=0..S-1$;
• the final partial block has length $(T \bmod m)+1$.

So

$pref(T)=xor(W_k[0..S-1])$ xor $W_k[S]$ if the partial length is odd.

Now we only need prefix XORs of $W_k$.

Each full period of $W_k$ has XOR $1$. For the remainder inside one period, recursively compute only the parities of how many $0$s, $1$s, and $2$s appear in the prefix. The same maps $A$ and $B$ transform those parities. The XOR of such a prefix is then:

• include $1$ if the count of value $1$ is odd;
• include $2$ if the count of value $2$ is odd.

Everything is $O(\log d)$ per input line. The final answer is the XOR of all individual games. Nonzero means Bug wins; zero means Feature wins. Same old Sprague-Grundy tax, just with more bit nonsense than anyone asked for.