取石子游戏 Nim 在全世界都非常有名，其规则十分简单。游戏开始时，有若干堆石子。两名玩家轮流从某一堆中取走至少一颗石子。无法进行合法移动的玩家输掉游戏。

8 月 17 日是一个非常特殊的日子，Rounddog 和 Calabash 创造了另一种属于他们自己的取石子游戏。新规则如下：

游戏开始时，Calabash 从右口袋里掏出一个字符串 $S$ 作为游戏的基石，游戏总共进行 $m$ 轮。

每一轮开始时，他们的共同好友 Severus 会从 $S$ 中选择一个子串 $T$。然后，在正式开始游戏之前，还有三个准备阶段。

在第一阶段，Calabash 将从 $S$ 中选择一个或多个不同的子串，使得它们都以 $T$ 为后缀。例如，“ris”是“claris”的后缀。一个字符串也被视为其自身的后缀。

第二阶段需要一些魔法力量。Calabash 将他选择的所有字符串转化为石子堆。具体来说，对于他选择的每个字符串 $X$，它将变成一堆石子，石子数量为 $W_p$，其中 $p$ 是 $X$ 在 $S$ 中出现的次数。例如，$X = \text{“aba”}$ 在 $S = \text{“ababa”}$ 中出现了两次，因此它将变成一堆两颗石子的石子堆。

第三阶段由 Rounddog 负责。在 Severus 和 Calabash 完成他们的操作后，Rounddog 从 Calabash 选择的石子堆中挑选一些扔掉。但 Rounddog 不能扔掉 Calabash 选择的所有石子堆，因为那样游戏会立即结束。

利用剩下的石子堆，Rounddog 和 Calabash 开始进行经典的 Nim 游戏。Calabash 先手。

现在，我们敬爱的 Quailty 想知道，如果 Calabash 和 Rounddog 都采取最优策略，Calabash 在每一轮中是否会获胜。此外，他还希望你计算出 Calabash 在第二阶段可以创造的石子总数最大值，使得在双方都采取最优策略的情况下，他仍然能够获胜。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 3$)，表示测试用例的数量。

每个测试用例中，第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)。

第二行包含一个长度为 $n$ 的字符串 $S$，由小写英文字母组成。

第三行包含 $n$ 个整数，第 $i$ 个整数为 $W_i$ ($1 \le W_i < 2^{58}$)。

第四行包含一个整数 $m$ ($1 \le m \le 200\,000$)，表示轮数。

接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，表示在这一轮中，Severus 将选择 $S[l, r]$ 作为字符串 $T$。

输出格式

对于每个测试用例，输出 $m$ 行，每行对应一轮的结果。在每一行中，打印出 Calabash 在第二阶段可以创造的石子总数最大值，使得在双方都采取最优策略的情况下他仍然获胜；如果他总是输，则输出 $-1$。

样例

输入 1

1
5
aabab
1 3 5 7 9
5
1 1
1 2
2 2
2 3
3 5

输出 1

6
1
6
4
1