33OJ
登录 注册

#P17494. [ICPC 2026 Wuhan I] Sequence Operations

    ID: 20222 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>Special JudgeICPC2026Ad-hoc省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Sequence Operations

Problem Description

Given a sequence of nn non-negative integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n, and two sequences of length mm, c1,c2,⋯ ,cmc_1,c_2,\cdots,c_m and x1,x2,⋯ ,xmx_1,x_2,\cdots,x_m. It is guaranteed that all xix_i are positive integers.

You need to perform mm operations in order from 11 to mm. In the ii-th operation, you modify the current sequence aa based on the value of cic_i:

  • If ci=1c_i=1, you must perform aj←mex⁡(aj,xi)a_j\leftarrow\operatorname{mex}(a_j,x_i) for all aja_j.
  • If ci=2c_i=2, you must perform aj←gcd⁡(aj,xi)a_j\leftarrow\gcd(a_j,x_i) for all aja_j.
  • If ci=0c_i=0, you can freely choose to perform either of the two operations mentioned above.

After all mm operations are completed, determine whether it is possible to make all elements in sequence aa equal.

Additional notes regarding the mex⁡\operatorname{mex} and gcd⁡\gcd operations are as follows:

  • The binary operation mex⁡(u,v)\operatorname{mex}(u,v) is defined as the smallest non-negative integer that is not equal to uu and not equal to vv. For example: mex⁡(0,1)=2\operatorname{mex}(0,1)=2, mex⁡(2,2)=0\operatorname{mex}(2,2)=0.
  • For the greatest common divisor gcd⁡\gcd, it is specifically defined that gcd⁡(0,x)=x\gcd(0,x)=x.

Input Format

The input contains multiple test cases. The first line contains an integer TT (1≤T≤1041 \le T \le 10^4), the number of test cases.

For each test case:

  • The first line contains two integers n,mn,m (1≤n,m≤3×1051 \le n,m \le 3\times10^5), representing the length of sequence aa and the number of operations.
  • The second line contains nn non-negative integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n (0≤aj≤1090 \le a_j \le 10^9), representing the initial sequence.
  • The next mm lines each contain two integers ci,xic_i,x_i (0≤ci≤20 \le c_i \le 2, 1≤xi≤1091 \le x_i \le 10^9), representing the type parameter and value parameter of the ii-th operation.

It is guaranteed that across all test cases, ∑n≤3×105\sum n \le 3\times10^5 and ∑m≤3×105\sum m \le 3\times10^5.

Output Format

For each test case, output one line. If it is possible to make all numbers equal after all operations are finished, output “Yes”; otherwise, output “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

Hint

For the first test case: in the first operation, choose to apply the gcd⁡\gcd operation, and the sequence becomes [1,1,1,1,1,1,1,1][1,1,1,1,1,1,1,1]. In the following 55 operations, no matter which operation you choose, the elements of the sequence will always remain equal, so output “Yes”.

For the second test case: the only operation is c1=1c_1=1, x1=1x_1=1, so you can only choose the mex⁡\operatorname{mex} operation.

  • a1←mex⁡(0,1)=2a_1\leftarrow\operatorname{mex}(0,1)=2
  • a2←mex⁡(1,1)=0a_2\leftarrow\operatorname{mex}(1,1)=0
  • a3←mex⁡(2,1)=0a_3\leftarrow\operatorname{mex}(2,1)=0

The final sequence becomes [2,0,0][2,0,0], and it is impossible to make all numbers equal, so output “No”.