QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
[+20]
Statistics

小 Y 和小 S 在玩一个游戏。

给定正整数 m,定义基本集合为大小为 3,元素在 1m 内的集合。例如:给定 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} 都是基本集合。

对于一个 1m 的排列 p[1],p[2],,p[m] 与集合 S{1,2,,m},定义 fp(S) 为将 S 内每一个元素 x 置换为 p[x] 后所得到的集合,即 fp(S)={p[x]|xS}

对于两个长度为 k 的集合序列 A,B,定义 AB 等价当且仅当存在一个 1m 的排列 p,使得 A 置换排列 p 后得到 B,即对于所有 1ikfp(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 个正整数。第 3i2,3i1,3i1in)个正整数分别表示 A[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。

输入的第三行包含 3n 个正整数。第 3i2,3i1,3i1in)个正整数分别表示 B[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。

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

输出格式

输出 q 行,每行包含一个字符串 YesNo,表示对应询问的两个序列是否等价。

样例一

输入

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]B1B2,因此这些询问的两个序列都不等价。
  • 对于询问 (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}=B2fp(A3)={p[1],p[2],p[4]}={1,2,3}=B3fp(A4)={p[1],p[2],p[3]}={2,3,4}=B4,因此这些询问的两个序列都等价。

样例二

ex_2.inex_2.ans

这个样例满足测试点 13 的约束条件。

样例三

ex_3.inex_3.ans

这个样例满足测试点 8 的约束条件。

样例四

ex_4.inex_4.ans

这个样例满足测试点 15,16 的约束条件。

数据范围

对于所有测试数据保证:1n2×1053m6×1051q106

测试点编号 n m q
13 50 4 50
46 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