{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn computer science, a trie, also called prefix tree, is a kind of search tree, an ordered tree data structure, where the keys are usually strings.\u003c/p\u003e\u003cp\u003eHere we have a trie with $$$(n + 1)$$$ nodes labelled $$$0$$$ through $$$n$$$, and its root is the node labelled by $$$0$$$. All edges in the trie are directed from nodes with lower heights to nodes with higher heights. Each of them contains only a lowercase letter, and any two edges with a common starting node have different characters.\u003c/p\u003e\u003cp\u003eWe would like to introduce a special matching on the trie for an arbitrary string $$$T[1..k]$$$.\u003c/p\u003e\u003cp\u003eThe matching will start at the root, consider all characters $$$T[1], T[2], \\cdots, T[k]$$$ in order, and move along some edge which starts from the current node and contains the currently considered character. If the matching arrives at some node but fails to move along some edge, then:\u003c/p\u003e\u003cul\u003e \u003cli\u003e it will record a failure at the current character, skip the character and move back to the root; and \u003c/li\u003e\u003cli\u003e it will consider the next character in the next match step because \u003cspan class\u003d\"tex-font-style-bf\"\u003efailed characters should be skipped\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFinally, after considering all characters in $$$T$$$, the matching will stay at a node indicating the destination of the matching on the trie. We denote the label of the destination as $$$Dest(T)$$$, and the total number of failures during the matching process as $$$CFail(T)$$$.\u003c/p\u003e\u003cp\u003eNow we give you a string with lowercase letters of length $$$m$$$ denoted by $$$S[1..m]$$$, and you need to answer $$$q$$$ queries. A query is defined as\u003c/p\u003e\u003cp\u003e$$$$$$Query(l, r) \u003d (CFail(S[l..r]), Dest(S[l..r])),$$$$$$\u003c/p\u003e\u003cp\u003ewhich asks the total number of failures and the destination of the matching for $$$S[l..r]$$$, a substring of $$$S$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ indicating the number of nodes in the trie, the length of given string $$$S$$$ and the total number of queries respectively, where $$$1 \\leq n, m, q \\leq 10^5$$$.\u003c/p\u003e\u003cp\u003eThe following $$$n$$$ lines describe the trie. The $$$i$$$-th line of them contains an integer $$$f_i$$$, satisfying $$$0 \\leq f_i \u0026lt; i$$$, and a lowercase letter $$$c_i$$$ describing the parent node of the $$$i$$$-th node and the character of the edge between them respectively.\u003c/p\u003e\u003cp\u003eThe next line contains a string in all lowercase letters indicating the given string $$$S$$$ of length $$$m$$$.\u003c/p\u003e\u003cp\u003eEach of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ indicating a query $$$Query(l, r)$$$, where $$$1 \\leq l \\leq r \\leq m$$$.\u003c/p\u003e\u003cp\u003eWe guarantee that the sum of $$$n$$$, the sum of $$$m$$$ and the sum of $$$q$$$ in all test cases are up to $$$10^6$$$ respectively.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output several lines to answer all queries.\u003c/p\u003e\u003cp\u003eFor each query output a line containing two integers in a line indicating $$$CFail(S[l..r])$$$ and $$$Dest(S[l..r])$$$ respectively. You should output exactly one whitespace between these two numbers.\u003c/p\u003e"}},{"title":"Examples","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\n5 10 5\n0 a\n0 b\n1 a\n1 c\n2 a\naaacbaacab\n1 5\n1 6\n1 7\n3 9\n4 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 2\n2 5\n3 0\n2 1\n4 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe figure below shows the trie given in the sample test case.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/08c0b7835c0ffb64df0a68da26b46056?v\u003d1715429614\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003ePaths for all queries are described as following, where each $$$\\Longrightarrow$$$ indicates a failure.\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$Path(1, 5) \u003d Path(\\unicode{x201C}\\texttt{aaacb}\\unicode{x201D}) \u003d 0 \\longrightarrow 1 \\longrightarrow 3 \\Longrightarrow 0 \\Longrightarrow 0 \\longrightarrow 2;$$$ \u003c/li\u003e\u003cli\u003e $$$Path(1, 6) \u003d Path(\\unicode{x201C}\\texttt{aaacba}\\unicode{x201D}) \u003d 0 \\longrightarrow 1 \\longrightarrow 3 \\Longrightarrow 0 \\Longrightarrow 0 \\longrightarrow 2 \\longrightarrow 5;$$$ \u003c/li\u003e\u003cli\u003e $$$Path(1, 7) \u003d Path(\\unicode{x201C}\\texttt{aaacbaa}\\unicode{x201D}) \u003d 0 \\longrightarrow 1 \\longrightarrow 3 \\Longrightarrow 0 \\Longrightarrow 0 \\longrightarrow 2 \\longrightarrow 5 \\Longrightarrow 0;$$$ \u003c/li\u003e\u003cli\u003e $$$Path(3, 9) \u003d Path(\\unicode{x201C}\\texttt{acbaaca}\\unicode{x201D}) \u003d 0 \\longrightarrow 1 \\longrightarrow 4 \\Longrightarrow 0 \\longrightarrow 1 \\longrightarrow 3 \\Longrightarrow 0 \\longrightarrow 1;$$$ \u003c/li\u003e\u003cli\u003e $$$Path(4, 10) \u003d Path(\\unicode{x201C}\\texttt{cbaacab}\\unicode{x201D}) \u003d 0 \\Longrightarrow 0 \\longrightarrow 2 \\longrightarrow 5 \\Longrightarrow 0 \\Longrightarrow 0 \\longrightarrow 1 \\Longrightarrow 0.$$$ \u003c/li\u003e\u003c/ul\u003e"}}]}