说明

给定一棵无限完全二叉树，其顶点用正整数标记。根节点为顶点 $1$，对于每个顶点 $x$（$x \geq 2$），其父节点是 $\left\lfloor \frac{x}{2} \right\rfloor$。

同时给定一个长度为 $N$ 的字符串 $S = S_0 S_1 \ldots S_{N-1}$。$S$ 的每个字符是 L 或 R。

考虑以下过程：你当前位于某个顶点 $u$，希望通过在树中反复移动到达顶点 $v$。

在第 $i$ 次移动（从 1 开始计数）时，假设你位于顶点 $x$。你可以选择以下移动之一：

向下移动： 如果 $S_{(i-1) \bmod N}$ 是 L，则移动到顶点 $2x$。否则，移动到顶点 $2x + 1$。

向上移动： 仅当 $x \geq 2$ 时可以选择。移动到顶点 $\left\lfloor \frac{x}{2} \right\rfloor$。

注意，你不能停留在同一个顶点。

给定 $Q$ 个独立的询问。在第 $i$ 个询问中，你从顶点 $u_i$ 出发，想要到达顶点 $v_i$。

对于每个询问，判断是否可能从 $u_i$ 到达 $v_i$。如果可能，求出所需的最少移动次数。

输入格式

输入格式如下：

$$\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$ 和 $v_i$ 是整数。
• $S$ 是一个长度为 $N$ 的字符串，由 L 和 R 组成。

输出格式

输出 $Q$ 行。在第 $i$ 行，如果可以从 $u_i$ 到达 $v_i$，则输出所需的最少移动次数；否则输出 -1。

5
LLRLR
3
1 12
9 2
913 2025

7
2
23

1
L
1
1 3

-1

提示

翻译由 DeepSeek V3.2 完成