Trail Ledger Calibration

Time limit: 6000 msMemory limit: 256 MB

A survey network consists of a tree with $N$ vertices numbered from $1$ to $N$ . Vertex $i$ carries an integer label $C_i$ .

The route ledger from vertex $U$ to vertex $V$ is the multiset of labels on the unique simple path from $U$ to $V$ , including both endpoints. The order of entries in a route ledger is irrelevant, while repeated labels remain repeated.

Each request gives two routes, one from $U$ to $V$ and another from $X$ to $Y$ , together with an allowance $K$ . You may change the labels of at most $K$ entries in the first route ledger. Each changed entry may receive any integer label between and , inclusive.

Determine whether the first route ledger can be made exactly equal to the second route ledger as a multiset.

Changes are hypothetical and apply only to the first ledger of the current request. They do not modify the tree or any other request. If the two routes share a vertex, its occurrence in each ledger is considered separately.

Input

The first line contains two integers $N$ and $Q$ , the number of vertices and the number of requests, respectively.

The second line contains $N$ integers $C_1, C_2, \ldots, C_N$ , where is the label of vertex .

Output

For each request, print YES if the first route ledger can be made equal to the second route ledger by changing at most $K$ entries. Otherwise, print NO.

The answer is case-sensitive.

Samples

Sample 1

Input

6 5
1 2 1 3 2 4
1 2
2 3
2 4
4 5
4 6
3 5 1 6 1
3 5 1 6 0
3 1 5 6 2
3 1 5 6 1
2 4 4 6 1

Output

YES
NO
YES
NO
YES

For the first two requests, the route ledgers are $\{1,2,2,3\}$ and $\{1,2,3,4\}$ . One change is sufficient, but zero changes are not. The next pair of route ledgers requires two changes. In the final request, changing the entry labeled $2$ to makes the ledgers equal.

Trail Ledger Calibration

Input

Output

Samples

Sample 1

Submit

Submissions