G-C-D, Unlucky!

We need decide whether some hidden array $a$ could produce the given prefix GCDs $p$ and suffix GCDs $s$.

The tempting wrong move is to try to reconstruct $a$ greedily. Don't. GCD constraints are nasty if you poke them directly, but they become clean if you build the smallest forced value at every position.

What must be true about one position?

If $p_i = \gcd(a_1,\dots,a_i)$, then $p_i$ divides every element among $a_1,\dots,a_i$, especially $a_i$.

If $s_i = \gcd(a_i,\dots,a_n)$, then $s_i$ divides every element among $a_i,\dots,a_n$, especially $a_i$.

So every valid $a_i$ must be divisible by both $p_i$ and $s_i$. Therefore it must be divisible by

$$b_i = \operatorname{lcm}(p_i, s_i).$$

This gives us a very natural candidate array $b$. The claim is:

There exists a valid array $a$ if and only if the array $b_i = \operatorname{lcm}(p_i,s_i)$ has prefix GCDs exactly $p$ and suffix GCDs exactly $s$.

So the algorithm is stupidly simple in the best way:

1. Build $b_i = \operatorname{lcm}(p_i,s_i)$.
2. Compute prefix GCDs of $b$.
3. Compute suffix GCDs of $b$.
4. Compare them to $p$ and $s$.

If both match, print Yes; otherwise print No.

Why this works

First, if $b$ passes the check, then obviously the answer is Yes, because $b$ itself is a valid hidden array.

The real question is: if some valid $a$ exists, why must $b$ pass?

Assume a valid $a$ exists. Since $a_i$ is divisible by both $p_i$ and $s_i$, $b_i = \operatorname{lcm}(p_i,s_i)$ divides $a_i$.

Now look at a prefix ending at $i$.

Because $b_j \mid a_j$ for every $j$, we get

$$\gcd(b_1,\dots,b_i) \mid \gcd(a_1,\dots,a_i) = p_i.$$

So the prefix GCD of $b$ is at most $p_i$ in the divisibility sense.

But also, for every $j \le i$, a real prefix GCD array must satisfy $p_i \mid p_j$, since GCDs can only lose factors as the prefix grows. And $b_j$ is a multiple of $p_j$, so $b_j$ is also a multiple of $p_i$.

That means every $b_j$ in the prefix is divisible by $p_i$, so

$$p_i \mid \gcd(b_1,\dots,b_i).$$

Together:

$$\gcd(b_1,\dots,b_i) \mid p_i \quad\text{and}\quad p_i \mid \gcd(b_1,\dots,b_i),$$

so they are equal.

The suffix proof is the exact same thing flipped around. For every $j \ge i$, a real suffix GCD array satisfies $s_i \mid s_j$, and $b_j$ is a multiple of $s_j$, hence also a multiple of $s_i$. Combined with $b_j \mid a_j$, the suffix GCD of $b$ must equal $s_i$.

So if any solution exists, the lcm candidate works. No guessing, no backtracking, no weird constructive gymnastics.

Overflow note

$p_i,s_i \le 10^9$, so their LCM can be up to $10^{18}$. Use long long, and compute

$$\operatorname{lcm}(x,y)=\frac{x}{\gcd(x,y)}\cdot y.$$

This stays within signed 64-bit here because the worst case is about $10^{18}$, below $9.22\cdot 10^{18}$.

Complexity

Each test case is linear:

$$O(n \log A)$$

because every GCD costs logarithmic time. The total $n$ over all tests is $10^5$, so this is comfortably fast.