题目描述

我们有一个根节点为1的树，有N个顶点。顶点编号从1到N。

第i条边连接了顶点$A_i$ 和 $B_i$。

顶点i上有一个整数$X_i$。

给定$Q$个查询。对于第i个查询，给定一对整数$(V_i,K_i)$，回答以下问题。

• 问题：在以顶点$V_i$为根的子树中，找到第$K_i$大的整数值。

约束条件

• $2 \leq N \leq 10^5$
• $0\leq X_i\leq 10^9$
• $1\leq A_i,B_i\leq N$
• $1\leq Q \leq 10^5$
• $1\leq V_i\leq N$
• $1\leq K_i\leq 20$
• 给定的图是一棵树。
• 以顶点$V_i$为根的子树至少有$K_i$个顶点。
• 输入中的所有值都是整数。

输入

从标准输入读取的输入数据格式如下：

$N$ $Q$ $X_1$ $\ldots$ $X_N$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $V_1$ $K_1$ $\vdots$ $V_Q$ $K_Q$

输出

输出$Q$行，第$i$行应该包含对第$i$个查询的回答。

示例输入1

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

示例输出1

4
5

这个输入中给出的树如下所示。

对于第一个查询，以顶点$1$为根的子树中的顶点是$1, 2, 3, 4$和$5$，因此打印这些顶点上写的数中第$2$大的值$4$。
对于第二个查询，以顶点$2$为根的子树中的顶点是$2, 3, 5$，因此打印这些顶点上写的数中第$1$大的值$5$。

示例输入2

6 2
10 10 10 9 8 8
1 4
2 1
2 5
3 2
6 4
1 4
2 2

示例输出2

9
10

示例输入3

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

示例输出3

1
10
100
1000