{"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\"\u003eYou are given a tree of $N$ vertices.\u003cbr\u003e\u003cbr\u003eThe query is specified by two vertices $u,v$ and an integer $d$ .\u003cbr\u003e\u003cbr\u003eThis time, a pair of vertices is called good if the distance between them is not less than $d$ .\u003cbr\u003e\u003cbr\u003e(Here, distance between two vertices means the number of edges lying on the path between them.)\u003cbr\u003e\u003cbr\u003eIn each step, you can only move between good pair of vertices.\u003cbr\u003e\u003cbr\u003eNow your task is to calculate the minimum number of steps to reach $v$ , starting from $u$. If you can’t reach the destination, the answer is -1 for that query.\u003cbr\u003e\u003cbr\u003eA lot of queries are given to you to make this problem difficult.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple test cases. The first line of the input contains an integer $T(T\\leq 15 )$, the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case consists of the following lines:\u003cbr\u003e\u003cbr\u003eThe first line contains three integers $N(1\\leq N\\leq 2\\cdot 10^5$ denoting the number of vertices, $Q(1\\leq Q\\leq 10^6$ denoting the number of queries and $M(1\\leq M\\leq 2\\cdot 10^5$ denoting the upper bound of $d$.\u003cbr\u003e\u003cbr\u003eThe second line contains $N-1$ integers $f_2,f_3,\\cdots f_N$ ,representing $(i,f_i)$ is a tree edge for every $i(2\\leq i\\leq N,1\\leq f_i \u0026lt; i )$. \u003cbr\u003e\u003cbr\u003eThe third line contains six integers $u_1,v_1,d_1,A,B,C$\u003cbr\u003e$(1\\leq u_1,v_1\\leq N,0\\leq d_1\u0026lt;M,10^4\\leq A,B,C\\leq 2\\cdot 10^4$).\u003cbr\u003e\u003cbr\u003eThe first query is specified by $u_1,v_1,d_1$.\u003cbr\u003e\u003cbr\u003e The $i$ -th ($2\\leq i\\leq Q$ ) query is specified by $u_1,v_1,d_1$ , which are generated by the following rules:\u003cbr\u003e\u003cbr\u003e$u_i\u003d((A\\ u_{i-1} + B + ans_{i-1})\\ mod\\ N) + 1$\u003cbr\u003e$v_i \u003d ((B\\ v_{i-1} +C +ans_{i-1})\\ mod\\ N)+1$\u003cbr\u003e$d_i \u003d (C\\ D_{i-1} + A +ans_{i-1})\\ mod\\ M$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output an integer $S \u003d \\sum_{i\u003d1}^{Q} i\\cdot (ans_i+1)$."}},{"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\n6 9 5\r\n1 2 1 3 3\r\n6 3 0 10865 16947 15183\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e55\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}