北京大学数据结构与算法课程的助教小 Z 正在批改作业，作业的题目如下：

某公司需要对文件中的字符进行压缩编码。已知文件包含 $n$ 种字符，其中第 $i$ 种字符在文件中出现了 $a_i$ 次。要求采用哈夫曼编码算法，构造出对应的哈夫曼树。

在实际布置作业时，小 Z 给 $q$ 位同学分发的数据略有不同：
第 $i$ 位同学的输入数据是在第 $i-1$ 位同学的基础上，将 $a_{p_{i-1}}$ 修改为 $v_{i-1}$，其余部分保持不变（对于第 1 位同学的输入，即初始数据 $a$）。

然而，小 Z 注意到所有 $q$ 位同学提交的哈夫曼树居然结构完全一致。这些树包含 $2n-1$ 个节点，第 $i$ 种字符对应的叶子节点编号为 $i$，对于每个非叶节点 $j$（$n < j < 2n$），它有两个子节点：$son_{j,0}$ 和 $son_{j,1}$（满足 $1 \leq son_{j,0}, son_{j,1} < j$）。

小 Z 希望判断这些哈夫曼树是否可能由其对应输入数据根据标准哈夫曼树构建算法得出。在本题中，在数据 $a_i$ 上的标准哈夫曼树构建算法为：

1. 初始化一个集合 $T = \{T_1, T_2, \dots, T_n\}$，其中每棵树 $T_i$ 包含一个节点，该节点的权重为 $a_i$，编号为 $i$。
2. 重复以下步骤，直到 $T$ 中仅剩一棵树：
   • 从 $T$ 中选择一棵权重最小的树 $u$（若有多种选择方式，任选其一），并将其从 $T$ 中删除。
   • 再从 $T$ 中选择一棵权重最小的树 $v$（若有多种选择方式，任选其一），并将其从 $T$ 中删除。
   • 从编号范围 $n+1$ 到 $2n-1$ 中任意选取一个未使用的编号 $p$，作为新树的根节点，将 $u$ 和 $v$ 作为根节点 $p$ 的左右子树（顺序可任意交换）。
   • 新树的权重为 $u$ 和 $v$ 的权重之和，接着将新树加入集合 $T$。
3. 当 $T$ 中仅剩一棵树时，这棵树即为构造出的哈夫曼树。

现在，请你帮小 Z 判断 $q$ 位同学提交的树是否可能由其对应输入数据根据标准哈夫曼树构建算法得出。

Input

第一行两个正整数 $n, q$，表示字符个数，同学个数。

下面一行 $n$ 个正整数 $a_i$，表示第一位同学收到的数据。

下面 $n - 1$ 行，每行两个正整数，依次给出了 $son_{j, 0}, son_{j, 1}$ $(j = n+1 \sim 2n-1)$。

下面 $q-1$ 行，每行两个正整数 $p_i, v_i$。

Output

输出 $q$ 行，第 $i$ 行是一个 "YES" 或 "NO"：

• "YES" 表示第 $i$ 位同学提交的树可能由其对应输入数据根据标准哈夫曼树构建算法得出；
• "NO" 表示不可能。

Examples

Input

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

Output

YES
NO
YES
NO

Input

8 5
5 3 4 2 2 6 5 5
1 8
4 5
10 3
11 9
7 2
6 13
14 12
7 3
6 8
4 2
2 5

Output

NO
YES
YES
YES
NO

Scoring

本题采用捆绑测试，你只有通过一个子任务的所有测试点，才能获得该子任务的分数。

对于所有测试数据：$1 \leq n, q \leq 10^5, 1 \leq p_i \leq n$，$a_i, v_i \geq 1$，对于每位同学，它收到的 $a_i$ 的和不超过 $10^{15}$。

子任务 1 (30 分)：$1 \leq n, q \leq 1000$。

子任务 2 (20 分)：$1 \leq n, q \leq 10000$。

子任务 3 (30 分)：$1 \leq n, q \leq 50000$。

子任务 4 (20 分)：无特殊限制。