Rounddog와 돌 게임

Nim은 단순한 규칙으로 전 세계에 알려진 돌 가져가기 게임이다. 처음에 여러 개의 돌 더미가 있다. 두 플레이어가 번갈아 가며 더미 하나에서 돌을 적어도 한 개 가져간다. 합법적인 수를 둘 수 없는 플레이어가 진다.

8월 17일, 특별한 날에 Rounddog와 Calabash는 자신들만의 돌 가져가기 게임을 만든다. 새 규칙은 다음과 같다.

시작할 때 Calabash가 오른쪽 주머니에서 문자열 $S$를 꺼낸다. 이 문자열이 게임의 기준이며, 게임은 총 $m$ 라운드로 진행된다.

각 라운드가 시작될 때 공통 친구 Severus가 $S$의 부분 문자열 $T$를 고른다. 플레이어가 게임을 시작하기 전에 준비 단계가 세 번 있다.

1단계에서 Calabash는 접미사가 모두 $T$인 $S$의 부분 문자열을 하나 이상 고른다. 고른 문자열은 서로 달라야 한다. 예를 들어 "ris"는 "claris"의 접미사다. 문자열은 자기 자신의 접미사이기도 하다.

2단계에서 Calabash는 고른 문자열을 모두 돌 더미로 바꾼다. 고른 문자열 $X$마다 $W_p$개의 돌로 이루어진 더미가 생긴다. 여기서 $p$는 $S$에서 $X$가 나타나는 횟수다. 예를 들어 "aba"는 "ababa"에 두 번 나타나므로 돌 두 개짜리 더미가 된다.

3단계는 Rounddog가 맡는다. Severus와 Calabash가 수를 정한 뒤, Rounddog가 Calabash가 고른 더미 중 일부를 버린다. 모든 더미를 버릴 수는 없다. 그러면 게임이 바로 끝나기 때문이다.

남은 더미로 고전적인 Nim 게임을 한다. Calabash가 먼저 둔다.

우리의 소중한 Quailty는 두 플레이어가 최선을 다할 때 각 라운드에서 Calabash가 이기는지 알고 싶어 한다. 또 Calabash가 최선을 다해도 이길 수 있는 범위 안에서, 2단계에서 만들 수 있는 돌의 총개수의 최댓값도 구하고자 한다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 3$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 100\,000$)이 주어진다.

둘째 줄에는 길이가 $n$인 소문자 알파벳 문자열 $S$가 주어진다.

셋째 줄에는 $n$개의 정수 $W_i$ ($1 \le W_i < 258$)가 주어진다.

다음 줄에는 라운드 수 $m$ ($1 \le m \le 200\,000$)이 주어진다.

이어지는 $m$개의 줄에는 정수 $l$과 $r$ ($1 \le l \le r \le n$)이 주어진다. 이는 해당 라운드에서 Severus가 $T$로 $S[l, r]$을 고른다는 뜻이다.

각 테스트 케이스마다 라운드당 한 줄씩, 총 $m$개의 줄을 출력한다. 각 줄에는 그 라운드의 2단계에서 Calabash가 최선을 다해 이길 수 있는 돌의 총개수 최댓값을 출력한다. Calabash가 항상 지는 경우에는 $-1$을 출력한다.