题目描述

给你一棵包含 $n$ 个节点的有根树，树上节点编号从 $1$ 到 $n$。根节点编号为 $1$。

树上每个节点有多有个权值，节点 $i$ 的权值为 $X_i$。

有 $q$ 次询问，第 $i$ 次询问表示为两个整数 $v_i$ 和 $k_i$，你需要回答出：

• 以节点 $v_i$ 为根的子树中所有节点的权值中第 $k_i$ 大的权值。

即：将节点 $v_i$ 为根的子树中每个节点的权值拿出来从大到小排个序后，排在第 $k_i$ 个位置的那个权值。

输入格式

第一行，两个整数 $n$ 和 $q$。

第二行，$n$ 个整数 $X_1, X_2, \ldots, X_n$，以空格分隔。

接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示树上一条边连接的两个端点。

接下来 $q$ 行，每行包含两个整数 $v_i$ 和 $k_i$，表示一次询问。

输出格式

对于每次询问，输出一行，包含一个整数。表示树上以节点 $v_i$ 为根的数字中第 $k_i$ 大的子树的权值。

样例

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

4
5

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

9
10

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

1
10
100
1000

说明/提示

数据规模与约定

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

对于 $100\%$ 的数据：

• $2 \le n \le 10^5$
• $0 \le X_i \le 10^9$
• $1 \le a_i, b_i \le n$，数据保证这是一棵树
• $1 \le q \le 10^5$
• $1 \le v_i \le n$
• $1 \le k_i \le 20$