{"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\"\u003eAndy and Andrew are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that\u0027s why they feel bored again and again. They just invented a new game, as they usually did.\u003cbr\u003e\u003cbr\u003eAt the beginning of the game, they write down one string $S\u003ds_1s_2s_3 \\ldots s_k$, and then they take turns(Andy first) to either:\u003cbr\u003e\u003cbr\u003e1. Erase the leftmost character from $S$, that is, $S\u003ds_2s_3s_4 \\ldots s_k$. \u003cbr\u003e2. Erase the rightmost character from $S$, that is, $S\u003ds_1s_2s_3 \\ldots s_{k-1}$.\u003cbr\u003e\u003cbr\u003eWhenever $S$ is empty or $S \\in A$ ($A$ is a given list of strings), the player which plays next loses the game.\u003cbr\u003e\u003cbr\u003eFor example, let $S\u003ddzxx$ and $A\u003d\\{z,dz\\}$. If Andy erases \u0027x\u0027 then Andrew can erase another \u0027x\u0027, because $S\u003ddz$ and $dz$ is in $A$, Andy, the next player, loses. Otherwise, Andy erases \u0027d\u0027, and then Andrew can erase \u0027z\u0027 result in a losing position for Andy.\u003cbr\u003e\u003cbr\u003eYou are given a string $T\u003dt_1t_2t_3\\ldots t_n$ and a list of string $A\u003d\\{a_1,a_2,\\ldots,a_m\\}$. Your task is to find who is the winner if $S$ is some substring of $T$. Andy and Andrew play so many times so you need to answer multiple queries.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $t$ indicating the total number of test cases. The following lines describe a test case.\u003cbr\u003e\u003cbr\u003eThe first line of each case contains three integers $n$, $m$, $q$, the length of $T$, the size of $A$, and the number of queries.The second line contains a string, representing $T$. Next $m$ lines, each line consists of a string, representing $a_i$. Next $q$ lines, each line consists of two integers $l,r$, representing a query that you should output who is the winner if $S\u003dt_lt_{l+1} \\ldots t_{r}$.\u003cbr\u003e\u003cbr\u003e$1 \\le t \\le 21$\u003cbr\u003e$1 \\le n, q \\le 40000$\u003cbr\u003e$1 \\le m \\le 10000$\u003cbr\u003e$1 \\le \\sum\\limits_{i\u003d1}^{m}|a_i| \\le 10000$\u003cbr\u003e$1 \\le l \\le r \\le n$\u003cbr\u003e$T$ and strings in $A$ consist of lowercase English letters.\u003cbr\u003eThere are at most 6 test cases with $n\u0026gt;5000$."}},{"title":"Output","value":{"format":"HTML","content":"For each query, if Andy wins, print \"1\" (without the quotes) on a single line, otherwise print \"0\" (without the quotes) on a single line."}},{"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\n10 4 10\r\nzzzabcdzxx\r\na\r\nz\r\ndz\r\nabcd\r\n1 3\r\n1 4\r\n3 6\r\n3 7\r\n3 8\r\n3 9\r\n4 4\r\n4 5\r\n5 5\r\n7 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n1\r\n1\r\n1\r\n0\r\n1\r\n0\r\n1\r\n1\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}