P15759 [JAG 2025 Summer Camp #1] Walking on Binary Tree

You are given an infinite complete binary tree whose vertices are labeled with positive integers. The root is vertex $1$, and for every vertex $x$ ($x \geq 2$), its parent is $\left\lfloor \frac{x}{2} \right\rfloor$. You are also given a string $S = S_0 S_1 \ldots S_{N-1}$ of length $N$. Each character of $S$ is either 'L' or 'R'. Consider the following process: you are currently at some vertex $u$, and want to reach vertex $v$ by repeatedly moving through the tree. On the $i$-th move (1-indexed), suppose you are at vertex $x$. You may choose one of the following moves: **Downward move:** If $S_{(i-1) \bmod N}$ is 'L', move to vertex $2x$. Otherwise, move to vertex $2x + 1$. **Upward move:** You can choose only if $x \geq 2$. Move to vertex $\left\lfloor \frac{x}{2} \right\rfloor$. Note that you cannot stay at the same vertex. You are given $Q$ independent queries. In the $i$-th query, you start at vertex $u_i$ and want to reach vertex $v_i$. For each query, determine whether it is possible to reach $v_i$ from $u_i$. If it is possible, find the minimum number of moves required.

The input is given in the following format: $$\begin{aligned} & N \\ & S \\ & Q \\ & u_1 \ v_1 \\ & u_2 \ v_2 \\ & \vdots \\ & u_Q \ v_Q \end{aligned}$$ - $1 \leq N \leq 10^6$ - $1 \leq Q \leq 200\ 000$ - $1 \leq u_i, v_i \leq 10^{18}$ ($1 \leq i \leq Q$) - $N, Q, u_i$ and $v_i$ are integers. - $S$ is a string of length $N$ consisting of 'L' and 'R'.

Output $Q$ lines. On the $i$-th line, print the minimum number of moves required to reach $v_i$ from $u_i$ if it is possible; otherwise, print "-1".