P17494 [ICPC 2026 Wuhan I] Sequence Operations

Given a sequence of $n$ non-negative integers $a_1,a_2,\cdots,a_n$, and two sequences of length $m$, $c_1,c_2,\cdots,c_m$ and $x_1,x_2,\cdots,x_m$. It is guaranteed that all $x_i$ are positive integers. You need to perform $m$ operations in order from $1$ to $m$. In the $i$-th operation, you modify the current sequence $a$ based on the value of $c_i$: - If $c_i=1$, you must perform $a_j\leftarrow\operatorname{mex}(a_j,x_i)$ for all $a_j$. - If $c_i=2$, you must perform $a_j\leftarrow\gcd(a_j,x_i)$ for all $a_j$. - If $c_i=0$, you can freely choose to perform either of the two operations mentioned above. After all $m$ operations are completed, determine whether it is possible to make all elements in sequence $a$ equal. Additional notes regarding the $\operatorname{mex}$ and $\gcd$ operations are as follows: - The binary operation $\operatorname{mex}(u,v)$ is defined as the smallest non-negative integer that is not equal to $u$ and not equal to $v$. For example: $\operatorname{mex}(0,1)=2$, $\operatorname{mex}(2,2)=0$. - For the greatest common divisor $\gcd$, it is specifically defined that $\gcd(0,x)=x$.

The input contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases. For each test case: - The first line contains two integers $n,m$ ($1 \le n,m \le 3\times10^5$), representing the length of sequence $a$ and the number of operations. - The second line contains $n$ non-negative integers $a_1,a_2,\cdots,a_n$ ($0 \le a_j \le 10^9$), representing the initial sequence. - The next $m$ lines each contain two integers $c_i,x_i$ ($0 \le c_i \le 2$, $1 \le x_i \le 10^9$), representing the type parameter and value parameter of the $i$-th operation. It is guaranteed that across all test cases, $\sum n \le 3\times10^5$ and $\sum m \le 3\times10^5$.

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”.

For the first test case: in the first operation, choose to apply the $\gcd$ operation, and the sequence becomes $[1,1,1,1,1,1,1,1]$. In the following $5$ 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 $c_1=1$, $x_1=1$, so you can only choose the $\operatorname{mex}$ operation. - $a_1\leftarrow\operatorname{mex}(0,1)=2$ - $a_2\leftarrow\operatorname{mex}(1,1)=0$ - $a_3\leftarrow\operatorname{mex}(2,1)=0$ The final sequence becomes $[2,0,0]$, and it is impossible to make all numbers equal, so output “No”.