Snake Instructions

Key Idea

The scary interactive shell is mostly a distraction. The whole thing collapses to one local obstruction: three occupied consecutive integer positions with speeds 010 or 020. If that exists, print $-1$. Otherwise, the speeds are uniquely recoverable, so in the hacked version we can just print the given speeds.

Important wording: consecutive means consecutive positions, i.e. positions $p,p+1,p+2$. Merely being adjacent in the input array is not enough. Gaps matter. Geometry is doing the work here, not vibes.

What Movement Means

During an instruction, all snakes move in the same direction, but snake $i$ moves with speed $s_i \in \{0,1,2\}$. If the signed movement of a speed-$1$ snake so far is $x$, snake $i$ is at

$a_i+s_i x.$

For the one-second instruction L, $x$ goes from $0$ to $-1$. So a snake can only die if it is on the right and is faster than a snake close enough on its left.

Since speeds are only $0,1,2$ and positions are integers, every death in the L query comes from one of these local patterns:

• 01: adjacent positions, speed $1$ hits speed $0$.
• 02: adjacent positions, speed $2$ hits speed $0$.
• 0_2: distance $2$, speed $2$ hits speed $0$.
• 12: adjacent positions, speed $2$ hits speed $1$.

Here _ means the integer position is empty. Tiny casework, but it punches way above its weight.

Why L And LR Are So Useful

Imagine asking L, then asking LR.

After the first L, some snakes may be removed. Now the remaining snakes move right for one second. No new collision can happen:

• If the left snake is not faster than the right snake, it obviously cannot catch it while moving right.
• If the left snake is faster, then during the previous L second it moved farther left, increasing their gap by exactly the amount it could close during the following R second. So it still cannot reach the right snake.

Therefore L and LR return the same survivor set. In LR, every survivor is back at its original coordinate. In L, that same survivor is at $a_i-s_i$.

So by matching survivors in order, every surviving snake gets its speed immediately:

$s_i = \text{position after `LR`} - \text{position after `L`}.$

Nice. The survivors just snitch on themselves.

What About The Dead Snakes?

Only the snakes killed by L remain unknown. From the four local death patterns above:

• 12 forces the dead snake to have speed $2$.
• 0_2 forces the dead snake to have speed $2$.
• If a dead snake has a dead neighbor immediately to its left, that left neighbor is not speed $0$, so the current snake must be speed $2$ to catch it.

After those forced speed-$2$ cases are handled, the only remaining uncertainty is between 01 and 02: a dead snake immediately to the right of a known speed-$0$ snake.

A query R resolves those cases unless there is a speed-$0$ snake immediately to the right too. If there is no adjacent zero on the right, speed $1$ and speed $2$ lead to different observable positions/collisions. If there is an adjacent zero on the right, both speed $1$ and speed $2$ die into one of the zeros during the first second, and the final observed board is identical.

That bad shape is exactly:

• 010
• 020

on positions $p,p+1,p+2$.

Why This Is Truly Impossible

Suppose positions $p,p+1,p+2$ contain speeds $0,x,0$, where $x\in\{1,2\}$.

Every valid instruction has a first character: L or R.

• If it starts with L, the middle snake hits the left speed-$0$ snake during the first second.
• If it starts with R, the middle snake hits the right speed-$0$ snake during the first second.

The middle snake dies before any answer is returned. Whether $x=1$ or $x=2$ only changes the hidden collision time, not the final response. The two zero-speed snakes stay put, and the rest of the board evolves the same way afterward.

So no clever adaptive strategy can distinguish 010 from 020. This is not a limitation of the simple strategy; it is genuinely impossible. The snake gets deleted before it can testify. Brutal courtroom procedure.

Hacked Version

In the hacked format, the speeds are already given. We do not need to simulate the interaction. The theorem above says:

• If there exists $i$ such that $a_{i-1}+1=a_i,\quad a_i+1=a_{i+1},\quad s_{i-1}=0,\quad s_i\ne 0,\quad s_{i+1}=0,$ then output $-1$.
• Otherwise, output the given speed array.

The scan is linear, so the total complexity is

$O\left(\sum n\right),$

with $O(n)$ memory per test case.