Let us solve the case \(s_1=\)L, \(s_{N+M}=\)R. The other cases can be solved similarly.

We will focus only on time when Snuke makes a turn (changes direction). For convenience, let us consider catching the last child as making a turn, too. Let \(k\) be the number of turns he makes at negative coordinates. If we first choose the set of children caught when making turns, there is exactly one \(s\) that realizes it, so let us consider the game’s duration for all sets of children caught when making turns.

Writing the game’s duration as a formula would involve an addition of some value for each turn. More specifically, if the child who starts at coordinate \(-L_i\) is caught at Snuke’s \(j\)-th turn at a negative coordinate, it contributes \(4L_i \times 9^{k-j}\) to the duration. Turns at positive coordinates can be represented similarly, so we focus on computing the contribution of negative turns.

The leftmost and rightmost children are always used in turns, so we pay attention to the others. Eventually, we have the following problem.

• For each \(1 \leq k\), find the sum below.
  • Choose \(k-1\) from the sequence \((L_1,L_2,\cdots,L_{N-1})\), and again \(k-1\) from \((R_1,R_2,\cdots,R_{M-1})\). For each of the ways to do so, if \(L_i\) is chosen in the \(j\)-th choice, add \(4L_i \times 9^{k-j}\) to the answer.

First, let us reverse \(L_i\) so that \(4L_i \times 9^j\) is added to the answer for the \(j\)-th value chosen. Next, rather than choosing \(k-1\) from \((R_1,R_2,\cdots,R_{M-1})\), let us choose \(M-k\) from \((R_1,R_2,\cdots,R_{M-1})\) that are not used in turns. If we let \(k\) move and take the sum, we are to try all ways to choose \(M-1\) in total from \(L\) and \(R\).

Eventually, we have the following problem.

• Choose \(M-1\) from a sequence of length \(N-1+M-1\). For each \(1 \leq i \leq N-1\), if \(i\) is chosen in the \(j\)-th choice, a weight of \(9^j\) is added. For each \(i\), find the total weight over all possible choices.

Writing this as a formula, we have \(\sum_j \binom{i-1}{j-1} \times \binom{N+M-2-i}{M-1-j} \times 9^j\) for each \(i\). This formula can be written as the product of a term depending on \(i\), a term depending on \(j\), and a term depending on \(i-j\), so we can use FFT to compute it for all \(i\) in \(O(N\log N)\) time.

The omitted contribution of the leftmost and rightmost children can be computed separately. Therefore, the problem can be solved in \(O(N \log N)\) time.