小 Y 和小 S 在玩一个游戏。
给定正整数 m,定义基本集合为大小为 3,元素在 1∼m 内的集合。例如:给定 m=4,则集合 {1,2,3} 与集合 {2,3,4} 都是基本集合。
定义集合序列为由基本集合构成的序列,例如,A=[{1,2,3},{2,3,4}] 是一个集合序列,其中 A[1]={1,2,3},A[2]={2,3,4} 都是基本集合。
对于一个 1∼m 的排列 p[1],p[2],…,p[m] 与集合 S⊆{1,2,…,m},定义 fp(S) 为将 S 内每一个元素 x 置换为 p[x] 后所得到的集合,即 fp(S)={p[x]|x∈S}。
对于两个长度为 k 的集合序列 A,B,定义 A 和 B 等价当且仅当存在一个 1∼m 的排列 p,使得 A 置换排列 p 后得到 B,即对于所有 1≤i≤k,fp(A[i])=B[i]。
给定两个长度为 n 的集合序列 A,B,有 q 次询问。每次小 S 会询问小 Y,在给定 l,r 的情况下,判断集合序列 [A[l],A[l+1],…,A[r]] 与集合序列 [B[l],B[l+1],…,B[r]] 是否等价。
时光荏苒,小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住,仅此而已。
输入格式
输入的第一行包含三个正整数 n,m,q,分别表示集合序列的长度、元素范围和询问次数。
输入的第二行包含 3n 个正整数。第 3i−2,3i−1,3i(1≤i≤n)个正整数分别表示 A[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。
输入的第三行包含 3n 个正整数。第 3i−2,3i−1,3i(1≤i≤n)个正整数分别表示 B[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。
接下来 q 行,每行包含两个正整数 l,r,表示一次询问。
输出格式
输出 q 行,每行包含一个字符串 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
解释
以下用 (l,r) 表示对 l,r 的询问。
- 对于询问 (1,1),令排列 p=[1,2,4,3],则 fp(A1)={p[1],p[2],p[3]}={1,2,4}=B[1],因此该询问的两个序列等价。
- 对于询问 (1,2),(1,3),(1,4),由于 A[1]=A[2] 但 B1≠B2,因此这些询问的两个序列都不等价。
- 对于询问 (2,2),(2,3),(2,4),(3,3),(3,4),(4,4),令排列 p=[2,3,4,1],则 fp(A2)={p[1],p[2],p[3]}={2,3,4}=B2,fp(A3)={p[1],p[2],p[4]}={1,2,3}=B3,fp(A4)={p[1],p[2],p[3]}={2,3,4}=B4,因此这些询问的两个序列都等价。
样例二
见 ex_2.in 与 ex_2.ans。
这个样例满足测试点 1∼3 的约束条件。
样例三
见 ex_3.in 与 ex_3.ans。
这个样例满足测试点 8 的约束条件。
样例四
见 ex_4.in 与 ex_4.ans。
这个样例满足测试点 15,16 的约束条件。
数据范围
对于所有测试数据保证:1≤n≤2×105,3≤m≤6×105,1≤q≤106。
测试点编号 | n≤ | m≤ | q≤ |
---|---|---|---|
1∼3 | 50 | 4 | 50 |
4∼6 | 5 | ||
7 | 200 | 4 | 200 |
8 | 5 | ||
9 | 4 | 2×105 | |
10 | 5 | ||
11 | 2×105 | 4 | |
12 | 5 | ||
13,14 | 2000 | 6000 | 103 |
15,16 | 106 | ||
17,18 | 2×104 | 6×104 | 102 |
19,20 | 2×105 | 6×105 | 106 |