给你一棵无限大的完全二叉树，其顶点用正整数标号。根节点为顶点 $1$，对于每个顶点 $x$ ($x \ge 2$)，其父节点为 $\lfloor \frac{x}{2} \rfloor$。

给你一个长度为 $N$ 的字符串 $S = S_0 S_1 \dots S_{N-1}$。$S$ 中的每个字符要么是 'L'，要么是 'R'。

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

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

• 向下移动：如果 $S_{(i-1) \bmod N}$ 是 'L'，则移动到顶点 $2x$。否则，移动到顶点 $2x + 1$。
• 向上移动：仅当 $x \ge 2$ 时可选。移动到顶点 $\lfloor \frac{x}{2} \rfloor$。

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

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

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

输入格式

输入按以下格式给出：

N
S
Q
u_1 v_1
u_2 v_2
:
u_Q v_Q

数据范围

• $1 \le N \le 10^6$
• $1 \le Q \le 200\,000$
• $1 \le u_i, v_i \le 10^{18}$ ($1 \le i \le Q$)
• $N, Q, u_i$ 和 $v_i$ 均为整数。
• $S$ 是一个长度为 $N$ 且仅由 'L' 和 'R' 组成的字符串。

输出格式

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

样例

输入样例 1

5
LLRLR
3
1 12
9 2
913 2025

输出样例 1

7
2
23

输入样例 2

1
L
1
1 3

输出样例 2

-1