Problem Description

Xiao Y and Xiao S are playing a game.

Given a positive integer $m$, define a basic set as a set of size $3$ whose elements are within $1\sim m$. For example, when $m=4$, the sets $\{1,2,3\}$ and $\{2,3,4\}$ are both basic sets.

Define a set sequence as a sequence made up 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,B$ of length $k$, define $A$ and $B$ to be equivalent if and only if there exists a permutation $p$ of $1\sim m$ such that applying the permutation $p$ to $A$ yields $B$. That is, for all $1\leq i\leq k$, $f_p(A[i])=B[i]$.

Given two set sequences $A,B$ of length $n$, there are $q$ queries. Each time, Xiao S asks Xiao Y: given $l,r$, determine whether the set sequence $[A[l],A[l+1],\dots,A[r]]$ and the set sequence $[B[l],B[l+1],\dots,B[r]]$ are equivalent.

Time flies, and Xiao S and Xiao Y will also drift apart. And the way we stay connected with someone is to remember, nothing more.

Input Format

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

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

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

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

Output Format

Output $q$ lines. Each line contains a string $\tt{Yes}$ or $\tt{No}$, indicating whether the two sequences in the corresponding query are equivalent.

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

Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

见 set2.in/ans
这个样例满足测试点 1-3 的约束条件。

见 set3.in/ans
这个样例满足测试点 8 的约束条件。

见 set4.in/ans
这个样例满足测试点 15、16 的约束条件。

Hint

[Sample 1 Explanation]

Below, $(l,r)$ denotes the query with parameters $l,r$:

• For query $(1,1)$, let the permutation be $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 for this query are equivalent.
• For queries $(1,2),(1,3),(1,4)$, since $A[1]=A[2]$ but $B[1]\neq B[2]$, the two sequences for these queries are all not equivalent.
• For queries $(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)$, let the permutation be $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$, $f_p(A_4)=\{p[1],p[2],p[3]\}=\{2,3,4\}=B_4$, so the two sequences for these queries are all equivalent.

[Constraints]

For all testdata, it is guaranteed that: $1\leq n\leq 2\times 10^5$, $3\leq m\leq 6\times 10^5$, $1\leq q\leq 10^6$, $1\leq l\leq r\leq n$.

::cute-table{tuack}

Translated by ChatGPT 5