题目描述
给定一个长度为 n 的非负整数序列 a1,a2,⋯,an,以及两个长度为 m 的序列 c1,c2,⋯,cm 和 x1,x2,⋯,xm。保证 xi 均为正整数。
你需要从 1 到 m 依次顺序执行 m 次操作。在第 i 次操作中,你可以根据 ci 的值对当前的序列 a 进行修改:
- 若 ci=1,那么你只能对所有的 aj 执行 aj←mex(aj,xi)。
- 若 ci=2,那么你只能对所有的 aj 执行 aj←gcd(aj,xi)。
- 若 ci=0,你可以自由选择执行上述两种操作中的任意一种。
在所有 m 次操作执行完毕后,判断最后能不能让序列 a 中的所有数都相等。
关于运算 mex 和 gcd 的额外说明如下:
- 定义二元操作 mex(u,v) 表示不等于 u 且不等于 v 的最小非负整数。例如:mex(0,1)=2,mex(2,2)=0。
- 对于最大公约数 gcd,特别定义 gcd(0,x)=x。
输入格式
输入包含多组测试数据。第一行包含一个整数 T(1≤T≤104),表示测试数据组数。
对于每组测试数据:
- 第一行包含两个整数 n,m(1≤n,m≤3×105),分别表示序列 a 的长度和操作的次数。
- 第二行包含 n 个非负整数 a1,a2,⋯,an(0≤aj≤109),表示初始序列。
- 接下来 m 行,第 i 行包含两个整数 ci,xi(0≤ci≤2,1≤xi≤109),表示第 i 次操作的类型参数和数值参数。
保证所有测试数据中 ∑n≤3×105 且 ∑m≤3×105。
输出格式
对于每组测试数据输出一行。如果在所有操作结束后能让所有数都相等,则输出 “Yes”;否则输出 “No”。
7
8 6
3 1 4 1 5 9 2 6
0 1
0 1
0 4
0 5
0 1
0 4
3 1
0 1 2
1 1
3 1
0 1 2
2 1
4 2
3 3 5 0
1 1
2 3
2 2
3 0
2 4
2 2
4 2
3 0 2 0
1 1
1 3
3 4
1 4 0
1 1
1 1
0 4
2 2
Yes
No
Yes
No
No
No
Yes
提示
对于第一组数据:在第一次操作时,选择执行 gcd 操作,序列将变为 [1,1,1,1,1,1,1,1]。在后续的 5 次操作中,你无论选择什么操作,序列元素始终会保持一致,因此输出 “Yes”。
对于第二组数据:唯一的一次操作是 c1=1,x1=1,你只能选择 mex 操作。
- a1←mex(0,1)=2
- a2←mex(1,1)=0
- a3←mex(2,1)=0
最终序列变为 [2,0,0],无法让所有数字相等,输出 “No”。