题目描述

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".

5
LLRLR
3
1 12
9 2
913 2025

7
2
23

1
L
1
1 3

-1