Xiao Z, a teaching assistant for the Data Structures and Algorithms course at Peking University, is grading assignments. The problem is as follows:

A company needs to compress characters in a file. It is known that the file contains $n$ types of characters, where the $i$-th character appears $a_i$ times. You are required to use the Huffman coding algorithm to construct the corresponding Huffman tree.

When assigning the homework, Xiao Z distributed slightly different data to $q$ students: The input data for the $i$-th student is based on the $(i-1)$-th student's data, with $a_{p_{i-1}}$ modified to $v_{i-1}$, while the rest remains unchanged (for the first student, the input is the initial data $a$).

However, Xiao Z noticed that the Huffman trees submitted by all $q$ students have identical structures. These trees contain $2n-1$ nodes, where the leaf node corresponding to the $i$-th character is labeled $i$. For each internal node $j$ ($n < j < 2n$), it has two children: $son_{j,0}$ and $son_{j,1}$ (satisfying $1 \leq son_{j,0}, son_{j,1} < j$).

Xiao Z wants to determine whether these Huffman trees could have been derived from their corresponding input data using the standard Huffman tree construction algorithm. In this problem, the standard Huffman tree construction algorithm for data $a_i$ is:

1. Initialize a set $T = \{T_1, T_2, \dots, T_n\}$, where each tree $T_i$ contains one node with weight $a_i$ and label $i$.
2. Repeat the following steps until only one tree remains in $T$:
   • Select a tree $u$ with the minimum weight from $T$ (if there are multiple, choose any one) and remove it from $T$.
   • Select another tree $v$ with the minimum weight from $T$ (if there are multiple, choose any one) and remove it from $T$.
   • Choose any unused label $p$ from the range $n+1$ to $2n-1$ as the root of a new tree, and set $u$ and $v$ as the left and right children of $p$ (the order can be swapped).
   • The weight of the new tree is the sum of the weights of $u$ and $v$, and then add the new tree to the set $T$.
3. When only one tree remains in $T$, this tree is the constructed Huffman tree.

Now, please help Xiao Z determine whether the trees submitted by the $q$ students could have been derived from their corresponding input data using the standard Huffman tree construction algorithm.

Input

The first line contains two positive integers $n$ and $q$, representing the number of characters and the number of students.

The next line contains $n$ positive integers $a_i$, representing the data received by the first student.

The next $n-1$ lines each contain two positive integers, giving $son_{j, 0}$ and $son_{j, 1}$ for $j = n+1 \sim 2n-1$ in order.

The next $q-1$ lines each contain two positive integers $p_i$ and $v_i$.

Output

Output $q$ lines, where the $i$-th line is "YES" or "NO":

• "YES" means the tree submitted by the $i$-th student could have been derived from their corresponding input data using the standard Huffman tree construction algorithm;
• "NO" means it is impossible.

Examples

Input 1

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

Output 1

YES
NO
YES
NO

Input 2

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 2

NO
YES
YES
YES
NO

Subtasks

This problem uses bundled testing; you only receive points for a subtask if you pass all test cases within that subtask.

For all test data: $1 \leq n, q \leq 10^5$, $1 \leq p_i \leq n$, $a_i, v_i \geq 1$. For each student, the sum of their $a_i$ does not exceed $10^{15}$.

Subtask 1 (30 points): $1 \leq n, q \leq 1000$.

Subtask 2 (20 points): $1 \leq n, q \leq 10000$.

Subtask 3 (30 points): $1 \leq n, q \leq 50000$.

Subtask 4 (20 points): No special restrictions.