{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn this problem you will have to help Berland army with organizing their command delivery system.\u003c/p\u003e\u003cp\u003eThere are $$$n$$$ officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer $$$a$$$ is the direct superior of officer $$$b$$$, then we also can say that officer $$$b$$$ is a direct subordinate of officer $$$a$$$.\u003c/p\u003e\u003cp\u003eOfficer $$$x$$$ is considered to be a subordinate (direct or indirect) of officer $$$y$$$ if one of the following conditions holds:\u003c/p\u003e\u003cul\u003e \u003cli\u003e officer $$$y$$$ is the direct superior of officer $$$x$$$; \u003c/li\u003e\u003cli\u003e the direct superior of officer $$$x$$$ is a subordinate of officer $$$y$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor example, on the picture below the subordinates of the officer $$$3$$$ are: $$$5, 6, 7, 8, 9$$$.\u003c/p\u003e\u003cp\u003eThe structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.\u003c/p\u003e\u003cp\u003eFormally, let\u0027s represent Berland army as a tree consisting of $$$n$$$ vertices, in which vertex $$$u$$$ corresponds to officer $$$u$$$. The parent of vertex $$$u$$$ corresponds to the direct superior of officer $$$u$$$. The root (which has index $$$1$$$) corresponds to the commander of the army.\u003c/p\u003e\u003cp\u003eBerland War Ministry has ordered you to give answers on $$$q$$$ queries, the $$$i$$$-th query is given as $$$(u_i, k_i)$$$, where $$$u_i$$$ is some officer, and $$$k_i$$$ is a positive integer.\u003c/p\u003e\u003cp\u003eTo process the $$$i$$$-th query imagine how a command from $$$u_i$$$ spreads to the subordinates of $$$u_i$$$. Typical DFS (depth first search) algorithm is used here.\u003c/p\u003e\u003cp\u003eSuppose the current officer is $$$a$$$ and he spreads a command. Officer $$$a$$$ chooses $$$b$$$ — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then $$$a$$$ chooses the one having minimal index. Officer $$$a$$$ gives a command to officer $$$b$$$. Afterwards, $$$b$$$ uses exactly the same algorithm to spread the command to its subtree. After $$$b$$$ finishes spreading the command, officer $$$a$$$ chooses the next direct subordinate again (using the same strategy). When officer $$$a$$$ cannot choose any direct subordinate who still hasn\u0027t received this command, officer $$$a$$$ finishes spreading the command.\u003c/p\u003e\u003cp\u003eLet\u0027s look at the following example:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4c032195c19c77cbe8a2e19729e00cfa?v\u003d1725638847\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eIf officer $$$1$$$ spreads a command, officers receive it in the following order: $$$[1, 2, 3, 5 ,6, 8, 7, 9, 4]$$$.\u003c/p\u003e\u003cp\u003eIf officer $$$3$$$ spreads a command, officers receive it in the following order: $$$[3, 5, 6, 8, 7, 9]$$$.\u003c/p\u003e\u003cp\u003eIf officer $$$7$$$ spreads a command, officers receive it in the following order: $$$[7, 9]$$$.\u003c/p\u003e\u003cp\u003eIf officer $$$9$$$ spreads a command, officers receive it in the following order: $$$[9]$$$.\u003c/p\u003e\u003cp\u003eTo answer the $$$i$$$-th query $$$(u_i, k_i)$$$, construct a sequence which describes the order in which officers will receive the command if the $$$u_i$$$-th officer spreads it. Return the $$$k_i$$$-th element of the constructed list or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e if there are fewer than $$$k_i$$$ elements in it.\u003c/p\u003e\u003cp\u003eYou should process queries independently. A query doesn\u0027t affect the following queries.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \\le n \\le 2 \\cdot 10^5, 1 \\le q \\le 2 \\cdot 10^5$$$) — the number of officers in Berland army and the number of queries.\u003c/p\u003e\u003cp\u003eThe second line of the input contains $$$n - 1$$$ integers $$$p_2, p_3, \\dots, p_n$$$ ($$$1 \\le p_i \u0026lt; i$$$), where $$$p_i$$$ is the index of the direct superior of the officer having the index $$$i$$$. The commander has index $$$1$$$ and doesn\u0027t have any superiors.\u003c/p\u003e\u003cp\u003eThe next $$$q$$$ lines describe the queries. The $$$i$$$-th query is given as a pair ($$$u_i, k_i$$$) ($$$1 \\le u_i, k_i \\le n$$$), where $$$u_i$$$ is the index of the officer which starts spreading a command, and $$$k_i$$$ is the index of the required officer in the command spreading sequence.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$q$$$ numbers, where the $$$i$$$-th number is the officer at the position $$$k_i$$$ in the list which describes the order in which officers will receive the command if it starts spreading from officer $$$u_i$$$. Print \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e\" if the number of officers which receive the command is less than $$$k_i$$$.\u003c/p\u003e\u003cp\u003eYou should process queries independently. They do not affect each other.\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\u003e9 6\n1 1 1 3 5 3 5 7\n3 1\n1 5\n3 4\n7 3\n1 8\n1 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6\n8\n-1\n9\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}