{"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\"\u003e Now Matt is preparing for the Graduate Record Examinations as Coach Pang did in 2013 and George did in 2011.\u003cbr\u003e\u003cbr\u003e Thanks to modern techniques, Matt uses automata instead of old-fasioned vocabulary books.\u003cbr\u003e\u003cbr\u003e The automata used by Matt is a directed acyclic graph (DAG) with N vertices and M edges. The vertices are conveniently numbered by 1, 2, . . . , N . Each edge is labeled with an integer. Additionally, some vertices are marked as special.\u003cbr\u003e\u003cbr\u003e A GRE word is obtained by concatenating the labels on the path from vertex 1 to a special vertex.\u003cbr\u003e\u003cbr\u003e Now, Matt has Q questions. The i-th question is asking for the length of ki-th smallest words among all the GRE words he can obtain in lexicographical order.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The first line contains only one integer T , which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003e For each test case, the first line contains three integers N, M, Q (2 ≤ N ≤ 10\u003csup\u003e5\u003c/sup\u003e, 0 ≤ M ≤ 10\u003csup\u003e5\u003c/sup\u003e, 1 ≤ Q ≤ 10\u003csup\u003e5\u003c/sup\u003e).\u003cbr\u003e\u003cbr\u003e The second line contains N - 1 integers s\u003csub\u003e2\u003c/sub\u003e, . . . , s\u003csub\u003en\u003c/sub\u003e. If the i-th vertex is special, then s\u003csub\u003ei\u003c/sub\u003e \u003d 1. Otherwise, s\u003csub\u003ei\u003c/sub\u003e \u003d 0. Vertex 1 is never special.\u003cbr\u003e\u003cbr\u003e Each of the following M lines contains three integers a\u003csub\u003ei\u003c/sub\u003e, b\u003csub\u003ei\u003c/sub\u003e, c\u003csub\u003ei\u003c/sub\u003e denoting an edge from vertex ai to vertex b\u003csub\u003ei\u003c/sub\u003e labeled with c\u003csub\u003ei\u003c/sub\u003e (1 ≤ a\u003csub\u003ei\u003c/sub\u003e, b\u003csub\u003ei\u003c/sub\u003e ≤ N, 1 ≤ c\u003csub\u003ei\u003c/sub\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e). For each vertex v, all outgoing edges are labeled with distinct integers.\u003cbr\u003e\u003cbr\u003e Each of the following Q lines contains the integer ki (1 ≤ k\u003csub\u003ei\u003c/sub\u003e ≤ 10\u003csup\u003e8\u003c/sup\u003e) of the i-th question."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, output “Case #x:” in the frirst line, where x is the case number (starting from 1).\u003cbr\u003e\u003cbr\u003e Then, for each question, output the length of the word in one line. If the word does not exist, output “-1” (without quotes) instead."}},{"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\n3 3 4\r\n1 1\r\n1 2 1\r\n1 3 12\r\n2 3 3\r\n1\r\n2\r\n3\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n1\r\n2\r\n1\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"There are 3 GRE words in total (sorted in lexicographical order): \u003cbr\u003e1. (1)\u003cbr\u003e2. (1, 3)\u003cbr\u003e3. (12)\u003cbr\u003e"}}]}