Xiao Y and Xiao S are playing a game.

Given a positive integer $m$, a basic set is defined as a set of size $3$ with elements in the range $1 \sim m$. For example, if $m=4$, both $\{1,2,3\}$ and $\{2,3,4\}$ are basic sets.

A set sequence is a sequence composed of basic sets. For example, $A=[\{1,2,3\},\{2,3,4\}]$ is a set sequence where $A[1]=\{1,2,3\}$ and $A[2]=\{2,3,4\}$ are both basic sets.

For a permutation $p[1],p[2],\dots,p[m]$ of $1 \sim m$ and a set $S\subseteq \{1,2,\dots,m\}$, define $f_p(S)$ as the set obtained by replacing each element $x$ in $S$ with $p[x]$, i.e., $f_p(S)=\{p[x]|x\in S\}$.

For two set sequences $A$ and $B$ of length $k$, $A$ and $B$ are defined as equivalent if and only if there exists a permutation $p$ of $1 \sim m$ such that $A$ transformed by $p$ results in $B$, i.e., for all $1\leq i\leq k$, $f_p(A[i])=B[i]$.

Given two set sequences $A$ and $B$ of length $n$, there are $q$ queries. In each query, Xiao S asks Xiao Y to determine whether the set sequence $[A[l],A[l+1],\dots,A[r]]$ is equivalent to the set sequence $[B[l],B[l+1],\dots,B[r]]$ for given $l$ and $r$.

Time passes, and Xiao S and Xiao Y will eventually drift apart. The way we stay connected to someone is by remembering them, and that is all.

Input

The first line contains three positive integers $n, m, q$, representing the length of the set sequences, the range of elements, and the number of queries, respectively.

The second line contains $3n$ positive integers. The $(3i - 2)$-th, $(3i - 1)$-th, and $(3i)$-th ($1 \le i \le n$) integers represent the three elements of $A[i]$. It is guaranteed that these three elements are in the range $[1, m]$ and are distinct.

The third line contains $3n$ positive integers. The $(3i - 2)$-th, $(3i - 1)$-th, and $(3i)$-th ($1 \le i \le n$) integers represent the three elements of $B[i]$. It is guaranteed that these three elements are in the range $[1, m]$ and are distinct.

The next $q$ lines each contain two positive integers $l, r$, representing a query.

Output

Output $q$ lines, each containing the string Yes or No, indicating whether the two sequences in the corresponding query are equivalent.

Examples

Input 1

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

Output 1

Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

Note 1

The notation $(l, r)$ denotes a query for the range $l, r$.

• For query $(1, 1)$, let the permutation $p = [1, 2, 4, 3]$. Then $f_p(A_1) = \{p[1], p[2], p[3]\} = \{1, 2, 4\} = B[1]$, so the two sequences are equivalent.
• For queries $(1, 2), (1, 3), (1, 4)$, since $A[1] = A[2]$ but $B_1 \ne B_2$, these sequences are not equivalent.
• For queries $(2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)$, let the permutation $p = [2, 3, 4, 1]$. Then $f_p(A_2) = \{p[1], p[2], p[3]\} = \{2, 3, 4\} = B_2$, $f_p(A_3) = \{p[1], p[2], p[4]\} = \{1, 2, 3\} = B_3$, and $f_p(A_4) = \{p[1], p[2], p[3]\} = \{2, 3, 4\} = B_4$. Thus, these sequences are all equivalent.

Input 2

See ex_2.in and ex_2.ans.

This sample satisfies the constraints of test cases $1 \sim 3$.

Input 3

See ex_3.in and ex_3.ans.

This sample satisfies the constraints of test case $8$.

Input 4

See ex_4.in and ex_4.ans.

This sample satisfies the constraints of test cases $15, 16$.

Constraints

For all test cases, it is guaranteed that: $1 \le n \le 2 \times 10 ^ 5$, $3 \le m \le 6 \times 10 ^ 5$, $1 \le q \le 10 ^ 6$.