Xiao A and Xiao B have arrived at the palace of the ancient gods.

They found $2n$ positive integers on the wall, not exceeding $n$, denoted as $f_1, f_2, \ldots, f_n$ and $g_1, g_2, \ldots, g_n$.

They found $m$ stone slabs on the ground, where the $i$-th slab has two positive integers $x_i$ and $y_i$ written on it, both not exceeding $n$.

According to legend, every second, $x_i$ changes to $f_{x_i}$ and $y_i$ changes to $g_{y_i}$. When $x_i = y_i$ (including the initial state), the $i$-th slab will crack.

Xiao A wants to know if each slab will crack, but he feels that waiting is too slow.

Xiao B tells Xiao A not to worry, but Xiao A is anxious, and you are also anxious, so you must help Xiao A find the answer within one second.

Input

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ positive integers $f_1, f_2, \ldots, f_n$.

The third line contains $n$ positive integers $g_1, g_2, \ldots, g_n$.

The next $m$ lines each contain two positive integers $x_i$ and $y_i$.

Output

Output $m$ lines. If the $i$-th slab will eventually crack, output YES on the $i$-th line; otherwise, output NO.

Examples

Input 1

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

Output 1

NO
YES
YES

Note

For the first slab, it can be proven that it will never crack.

For the second slab, the sequence of $(x_2, y_2)$ is $(1, 4) \rightarrow (2, 1) \rightarrow (3, 2) \rightarrow (4, 4) \rightarrow \cdots$, so it will crack after three seconds.

For the third slab, it cracks at the very beginning.

Input 2

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

Output 2

YES
NO
NO
NO
YES
NO
NO
YES
NO
YES

Note

For the eighth slab, $(5, 5)$ cracks at the very beginning.

Input 3

ex_wait3.in

Output 3

ex_wait3.ans

See ex_wait3.in/ex_wait3.ans in the provided files. This sample satisfies the special properties of Subtask 3.

Input 4

ex_wait4.in

Output 4

ex_wait4.ans

See ex_wait4.in/ex_wait4.ans in the provided files. This sample satisfies the special properties of Subtask 5.

Input 5

ex_wait5.in

Output 5

ex_wait5.ans

See ex_wait5.in/ex_wait5.ans in the provided files. This sample satisfies the special properties of Subtask 6.

Input 6

ex_wait6.in

Output 6

ex_wait6.ans

See ex_wait6.in/ex_wait6.ans in the provided files. This sample satisfies the special properties of Subtask 7.

Constraints

This problem uses bundled testing.

For all data, $1 \le n, m \le 10^5$ and $1 \le f_i, g_i, x_i, y_i \le n$.

For a given subtask, if the column for $h$ ($h$ being $f$ or $g$) is:

• A, then it satisfies $\forall 1 \le i < j \le n, h_i \ne h_j$.
• B, then it satisfies $\forall 1 \le i \le n, h_i \le i$.
• *, then the subtask (Subtask 4) satisfies $\forall 1 \le i \le n, f_i = g_i$.
• -, then there are no special restrictions.