该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D. 子树查询

题目描述

我们有一棵包含$n$个顶点的有根树。顶点按照编号从1到$n$进行标记，而根顶点为顶点1。 第$i$条边连接着顶点$a_i$和$b_i$。 顶点$i$上有一个整数$x_i$。

给定$q$个查询。对于第$i$个查询，给定一对整数$(v_i, k_i)$，求在以顶点$v_i$为根的子树中，第$k_i$大的整数值是多少？没有则输出 -1

输入格式

第一行输入两个整数$n, q$

第二行输入$n$个整数$x_1, x_2, \cdots, x_n$

接下来$n - 1$行，每行两个整数$a_i, b_i$

接下来$q$行，每行两个整数$v_i, k_i$

输出格式

输出$q$个行，每行一个整数表示答案

样例输入1

5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2 1

样例输出1

4
5

样例输入2

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

样例输出2

1
10
100
1000

数据范围

对于30%的数据，$n, q \leq 1000$

对于另外30%的数据，$k_i \leq 2$

对于100%的数据，$n, q \leq 10^5, 1 \leq v_i \leq n, 1 \leq k_i \leq 20$