|
||||||||||
Play Games with RounddogTime 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
Sample Output
Source | ||||||||||
|