{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAs 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.\u003cbr\u003e\u003cbr\u003eOn August 17th, a very special day, Rounddog and Calabash create another picking stones game of their own. The new rule is as the following.\u003cbr\u003e\u003cbr\u003eTo start with, Calabash takes out a string $S$ from his right pocket as the keystone of their game, which has $m$ round in total.\u003cbr\u003e\u003cbr\u003eAt 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.\u003cbr\u003e\u003cbr\u003eIn Phase 1, Calabash will select several \u003cb\u003edistinct\u003c/b\u003e substrings from $S$, satisfying that they all have a suffix $T$. Taking \"$\\texttt{claris}$\" as an example, one of its suffixes is \"$\\texttt{ris}$\". \u003cbr\u003e\u003cbr\u003ePhase 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.\u003cbr\u003e\u003cbr\u003eRounddog will be in charge of Phase 3. After Severus and Calabash\u0027s movement, Rounddog chooses some piles from Calabash\u0027s selection, and throws them away. But Rounddog can\u0027t throw all the piles Calabash selected, because it will lead the game to the end immediately.\u003cbr\u003e\u003cbr\u003eWith the left piles, Rounddog and Calabash will start playing based on the original rule of Picking Stones. Calabash always moves first. \u003cbr\u003e\u003cbr\u003eNow, 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 \u003cb\u003ethe maximum total number of stones\u003c/b\u003e Calabash can achieve in Phase 2 on the premise of his victory.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"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.\u003cbr\u003e\u003cbr\u003eIn each test case, the first line contains an integer $n~(1 \\le n \\le 100\\,000)$.\u003cbr\u003e\u003cbr\u003eThe second line contains a string $S$ of length $n$ with only lowercase English letters.\u003cbr\u003e\u003cbr\u003eThe third line contains $n$ integers, $i$-th of which is $W_i~(1 \\le W_i \u0026lt; 2^{58})$.\u003cbr\u003e\u003cbr\u003eThe fourth line contains an integer $m~(1 \\le m \\le 200\\,000)$, representing the number of games.\u003cbr\u003e\u003cbr\u003eEach 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$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"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.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5\r\naabab\r\n1 3 5 7 9\r\n5\r\n1 1\r\n1 2\r\n2 2\r\n2 3\r\n3 5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n1\r\n6\r\n4\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}