{"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\"\u003eThere are N boxes on the ground, which are labeled by numbers from 1 to N. The boxes are magical, the size of each one can be enlarged or reduced arbitrarily.\u003cbr\u003eJack can perform the “MOVE x y” operation to the boxes: take out box x; if y \u003d 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.\u003cbr\u003eIn the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/ca2211bcbb816aea985e8c6ed0e55923?v\u003d1715364489\"\u003e\u003cbr\u003eThe picture below shows the state after Jack performs “MOVE 4 1”:\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/5e040d283bdaf5b4baf2171a908713cd?v\u003d1715364489\"\u003e\u003cbr\u003eThen he performs “MOVE 3 0”, the state becomes:\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/e7d99f7eb38b0321e8058a92d5ec47b1?v\u003d1715364489\"\u003e\u003cbr\u003eDuring a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input contains several test cases.\u003cbr\u003eFor each test case, the first line has an integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 50000), representing the number of boxes.\u003cbr\u003eNext line has N integers: a1, a2, a3, ... , aN (0 \u0026lt;\u003d ai \u0026lt;\u003d N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).\u003cbr\u003eNext line has an integer M (1 \u0026lt;\u003d M \u0026lt;\u003d 100000), representing the number of MOVE operations and queries.\u003cbr\u003eOn the next M lines, each line contains a MOVE operation or a query:\u003cbr\u003e1.\u0026nbsp;\u0026nbsp;MOVE x y, 1 \u0026lt;\u003d x \u0026lt;\u003d N, 0 \u0026lt;\u003d y \u0026lt;\u003d N, which is described above. If an operation is illegal, just ignore it.\u003cbr\u003e2.\u0026nbsp;\u0026nbsp;QUERY x, 1 \u0026lt;\u003d x \u0026lt;\u003d N, output the root box of box x.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each query, output the result on a single line. Use a blank line to separate each test case."}},{"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\u003e2\r\n0 1\r\n5\r\nQUERY 1\r\nQUERY 2\r\nMOVE 2 0\r\nMOVE 1 2\r\nQUERY 1\r\n6\r\n0 6 4 6 1 0\r\n4\r\nMOVE 4 1\r\nQUERY 3\r\nMOVE 1 4\r\nQUERY 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1\r\n2\r\n\r\n1\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}