{"raw_statement":[{"iden":"problem statement","content":"We have a rooted tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the root is Vertex $1$.  \nThe $i$\\-th edge connects Vertices $A_i$ and $B_i$.  \nVertex $i$ has an integer $X_i$ written on it.\nYou are given $Q$ queries. For the $i$\\-th query, given a pair of integers $(V_i,K_i)$, answer the following question.\n\n*   Question: among the integers written on the vertices in the subtree rooted at Vertex $V_i$, find the $K_i$\\-th largest value."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $0\\leq X_i\\leq 10^9$\n*   $1\\leq A_i,B_i\\leq N$\n*   $1\\leq Q \\leq 10^5$\n*   $1\\leq V_i\\leq N$\n*   $1\\leq K_i\\leq 20$\n*   The given graph is a tree.\n*   The subtree rooted at Vertex $V_i$ has $K_i$ or more vertices.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$X_1$ $\\ldots$ $X_N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n$V_1$ $K_1$\n$\\vdots$\n$V_Q$ $K_Q$"},{"iden":"sample input 1","content":"5 2\n1 2 3 4 5\n1 4\n2 1\n2 5\n3 2\n1 2\n2 1"},{"iden":"sample output 1","content":"4\n5\n\nThe tree given in this input is shown below.\n![image](https://img.atcoder.jp/ghi/e2bc1237d64f79f33181e6f54c9f7ce7.png)\nFor the $1$\\-st query, the vertices in the subtree rooted at Vertex $1$ are Vertices $1, 2, 3, 4$, and $5$, so print the $2$\\-nd largest value of the numbers written on these vertices, $4$.  \nFor the $2$\\-nd query, the vertices in the subtree rooted at Vertex $2$ are Vertices $2, 3$, and $5$, so print the $1$\\-st largest value of the numbers written on these vertices, $5$."},{"iden":"sample input 2","content":"6 2\n10 10 10 9 8 8\n1 4\n2 1\n2 5\n3 2\n6 4\n1 4\n2 2"},{"iden":"sample output 2","content":"9\n10"},{"iden":"sample input 3","content":"4 4\n1 10 100 1000\n1 2\n2 3\n3 4\n1 4\n2 3\n3 2\n4 1"},{"iden":"sample output 3","content":"1\n10\n100\n1000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}