F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Play Games with Rounddog

Time Limit: 8000/8000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 286    Accepted Submission(s): 87


Problem Description
As a typical Nim game, picking stones is very famous all over the world with its quite simple rule. Initially, there are several piles of stones. Two players take turns to remove at least one stone from one of the piles. Whoever cannot make any legal move loses this game.

On August 17th, a very special day, Rounddog and Calabash create another picking stones game of their own. The new rule is as the following.

To start with, Calabash takes out a string $S$ from his right pocket as the keystone of their game, which has $m$ round in total.

At the beginning of each round, their common friend Severus will select a substring $T$ from $S$. Then before they officially start playing, there are three phases need to be applied.

In Phase 1, Calabash will select several distinct substrings from $S$, satisfying that they all have a suffix $T$. Taking "$\texttt{claris}$" as an example, one of its suffixes is "$\texttt{ris}$".

Phase 2 requires some magical power. Calabash will turn all strings he selects to stone piles. Specifically, for each string $X$ he chooses, it will become a pile of $W_{p}$ stones where $p$ is the number of occurrences of $X$ in $S$. For example, "$\texttt{aba}$" occurs in "$\texttt{ababa}$" for 2 times.

Rounddog will be in charge of Phase 3. After Severus and Calabash's movement, Rounddog chooses some piles from Calabash's selection, and throws them away. But Rounddog can't throw all the piles Calabash selected, because it will lead the game to the end immediately.

With the left piles, Rounddog and Calabash will start playing based on the original rule of Picking Stones. Calabash always moves first.

Now, our beloved Quailty wants to know whether Calabash will win in each round if they both perform the optimal strategy. Furthermore, he also wants you to calculate the maximum total number of stones Calabash can achieve in Phase 2 on the premise of his victory.
 

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

In each test case, the first line contains an integer $n~(1 \le n \le 100\,000)$.

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

The third line contains $n$ integers, $i$-th of which is $W_i~(1 \le W_i < 2^{58})$.

The fourth line contains an integer $m~(1 \le m \le 200\,000)$, representing the number of games.

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

Output
For each test case, output $m$ lines, each of which contains an integer representing the maximum total number of stones Calabash can achieve on the premise of his victory, or $-1$ if he always loses.
 

Sample Input
1 5 aabab 1 3 5 7 9 5 1 1 1 2 2 2 2 3 3 5
 

Sample Output
6 1 6 4 1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 17:23:24, Gzip enabled