Play Games with Rounddog

Nim is a stone-picking game known around the world for its simple rules. At the start, there are several piles of stones. Two players take turns removing at least one stone from one of the piles. A player who cannot make a legal move loses.

On August 17th, a very special day, Rounddog and Calabash create a stone-picking game of their own. The new rules are as follows.

At the start, Calabash takes a string $S$ out of his right pocket. It is the keystone of their game, which has $m$ rounds in total.

At the beginning of each round, their common friend Severus selects a substring $T$ of $S$. Before the players start, there are three preparation phases.

In Phase 1, Calabash selects one or more distinct substrings of $S$ that all have $T$ as a suffix. For example, "ris" is a suffix of "claris". A string is a suffix of itself.

In Phase 2, Calabash turns every string he selected into a pile. For each selected string $X$, the pile has $W_p$ stones, where $p$ is the number of occurrences of $X$ in $S$. For example, "aba" occurs twice in "ababa", so it becomes a pile of two stones.

In Phase 3, Rounddog acts after Severus and Calabash have made their moves. Rounddog chooses some of Calabash's piles and throws them away. Rounddog cannot throw away all of the piles, because then the game would end immediately.

The remaining piles are played as the classic Nim game. Calabash moves first.

Quailty wants to know whether Calabash wins in each round if both players play optimally. He also wants the maximum total number of stones Calabash can create in Phase 2 such that he still wins with optimal play.

The first line contains a single integer $T$ ($1 \le T \le 3$), the number of test cases.

Each test case starts with an integer $n$ ($1 \le n \le 100\,000$).

The second line contains a string $S$ of length $n$ made of lowercase English letters.

The third line contains $n$ integers $W_i$ ($1 \le W_i < 258$).

The next line contains an integer $m$ ($1 \le m \le 200\,000$), the number of rounds.

Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$), meaning that in this round Severus selects $S[l, r]$ as $T$.

For each test case, print $m$ lines, one per round. Each line contains the maximum total number of stones Calabash can create in Phase 2 of that round so that he still wins with optimal play. If he always loses, print $-1$.