[NOI2024] 集合

给定正整数 $m$，定义基本集合为大小为 $3$、元素在 $1\sim m$ 内的集合。

集合序列是由基本集合构成的序列。对于一个 $1\sim m$ 的排列 $p$ 与集合 $S\subseteq\{1,2,\ldots,m\}$，定义

$$f_p(S)=\{p[x]\mid x\in S\}.$$

对于两个长度为 $k$ 的集合序列 $A,B$，称它们等价，当且仅当存在一个 $1\sim m$ 的排列 $p$，使得对于所有 $1\le i\le k$ 都有 $f_p(A[i])=B[i]$。

给定两个长度为 $n$ 的集合序列 $A,B$。有 $q$ 次询问，每次给出 $l,r$，判断

$$[A[l],A[l+1],\ldots,A[r]]$$

与

$$[B[l],B[l+1],\ldots,B[r]]$$

是否等价。

输入格式

第一行包含三个正整数 $n,m,q$，分别表示集合序列长度、元素范围和询问次数。

第二行包含 $3n$ 个正整数。第 $3i-2,3i-1,3i$ 个数表示 $A[i]$ 的三个元素；它们均在 $[1,m]$ 内且互不相同。

第三行以相同格式给出 $B[1],B[2],\ldots,B[n]$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

对每次询问输出一行 Yes 或 No。

样例输入

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

题包另含三组官方公开样例。

数据范围

对于所有测试数据：

• $1\le n\le2\times10^5$；
• $3\le m\le6\times10^5$；
• $1\le q\le10^6$；
• $1\le l\le r\le n$。

来源与许可

本题为 CCF NOI 2024 第一试第一题「集合（set）」。题面与测试数据来自 NOI 官网发布页，按 CC BY-NC 4.0 使用。原赛制使用 set.in / set.out 文件输入输出；本平台等价适配为标准输入输出。