During the game, let’s keep the following two values:

• \(L\), the number of consecutive empty cells to the left of Snuke (before the nearest block to that direction).
• \(R\), the number of consecutive empty cells to the right of Snuke (before the nearest block to that direction).

Only these two values matter because Snuke can never reach beyond these \(L + R + 1\) cells. Also, notice that if \(a \leq a'\) abd \(b \leq b'\), the state \((a', b')\) is not worse than \((a, b)\) for Snuke (to give a formal proof, use an induction on the number of remaining steps).

Thus, we can simulate the game as follows:

• We start with the state \((\infty, \infty)\).
• In Snuke’s turn, he may change the state \((L, R)\) to \((L+1, R-1)\) or \((L-1, R+1)\) (or may not).
• In your turn, you change the state \((L, R)\) to \((0, \min \{ L, R \})\).

For a given turn string, how to check the winner? For example, suppose that the turn string is \(S...SBS...SBS...SBS...SBS...SBS...S\), and run lengths of \(S\) are \(a, b, c, d, e, f\) from left to right.

• After the first \(B\), the state is \((0, \infty)\).
• Then Snuke changes the state to \((b, \infty)\).
• After the second \(B\), the state is \((0, b)\).
• Then, for Snuke, it is optimal to change the state to \((x, b-x)\), where \(x = \min \{ [b/2], c \}\).

By repeating this kind of observations, we get that Snuke wins iff \( \min \{ [b/8], [c/4], [d/2], e \} \geq 1\), or equivalently, \(b \geq 8, c \geq 4, d \geq 2, e \geq 1\).

Now we can get an \(O(N log N)\) DP solution to solve the original problem.