Equal LCM Subsets
Contest: CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3200
Tags: data structures, math, number theory

You are given two sets of positive integers $$$A$$$ and $$$B$$$. You have to find two non-empty subsets $$$S_A \subseteq A$$$, $$$S_B \subseteq B$$$ so that the least common multiple (LCM) of the elements of $$$S_A$$$ is equal to the least common multiple (LCM) of the elements of $$$S_B$$$.

Input format:
The input consists of multiple test cases. The first line of the input contains one integer $$$t$$$ ($$$1 \leq t \leq 200$$$), the number of test cases.

For each test case, there is one line containing two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$), the sizes of the sets $$$A$$$ and $$$B$$$, respectively.

The next line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 4 \cdot 10^{36}$$$), the elements of $$$A$$$.

The next line contains $$$m$$$ distinct integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 4 \cdot 10^{36}$$$), the elements of $$$B$$$.

The sum of $$$n$$$ for all test cases and the sum of $$$m$$$ for all test cases is at most $$$1000$$$.

Output format:
For each test case, if there do not exist two subsets with equal least common multiple, output one line with NO.

Otherwise, output one line with YES, followed by a line with two integers $$$|S_A|, |S_B|$$$ ($$$1 \leq |S_A| \leq n$$$, $$$1 \leq |S_B| \leq m$$$), the sizes of the subsets $$$S_A$$$ and $$$S_B$$$

The next line should contain $$$|S_A|$$$ integers $$$x_1, x_2, \ldots, x_{|S_A|}$$$, the elements of $$$S_A$$$, followed by a line with $$$|S_B|$$$ integers $$$y_1, y_2, \ldots, y_{|S_B|}$$$, the elements of $$$S_B$$$. If there are multiple possible pairs of subsets, you can print any.

Constraints:
Time limit: 10.0 s
Memory limit: 512.0 MB

Example input:
4
3 4
5 6 7
2 8 9 10
4 4
5 6 7 8
2 3 4 9
1 3
1
1 2 3
5 6
3 4 9 7 8
2 15 11 14 20 12

Example output:
NO
YES
1 2
6
2 3
YES
1 1
1
1
YES
3 2
3 7 4
12 14

Editorial:
First, we see how to check if the two entire sets have the same LCM (without subsets).
To do this, for each element $$$a \in A$$$ let us compute $$$$$$f(a, B) = \gcd(a/\gcd(a, b_1), \ldots, a/\gcd(a, b_n))$$$$$$ and check if it is $$$1$$$. If it is greater than $$$1$$$, that means $$$a$$$ has some prime power $$$p^k$$$ dividing it with exponent greater than any of the corresponding exponents in $$$B$$$, and therefore the LCM cannot be equal. We perform the same computations with the elements of $$$B$$$ (i.e., $$$f(b, A)$$$). If all the results were $$$1$$$, then the LCMs are equal. Complexity is $$$\mathcal O(n^2 \cdot U)$$$, where $$$U = \log(10^{36})$$$.
If $$$f(a, B) > 1$$$, we can simply delete $$$a$$$ from $$$A$$$ and solve recursively using the remaining sets (similarly if $$$f(b, A) > 1$$$). We need to update the values $$$f(a, B)$$$ and $$$f(b, A)$$$ efficiently. We can do it using many segment tree (one for each $$$a \in A$$$, and one for each $$$b \in B$$$).
The segment tree of $$$a \in A$$$, $$$ST_a$$$, will have the elements of $$$B$$$ as its leaves, and the node $$$u$$$ of $$$ST_a$$$, which will include a range $$$[i, j]$$$ of elements of $$$B$$$ will be $$$\gcd(a/\gcd(a, b_i), \ldots, a/\gcd(a, b_j))$$$, meaning that after removing an element of $$$B$$$, we will need to recompute all of the $$$n$$$ segment trees in $$$\mathcal O(\log n + U)$$$ time each (it is $$$\mathcal O(\log n + U)$$$ and not $$$\mathcal O(\log n \cdot U)$$$ by a similar argument to the one used to compute the complexity of computing the gcd of an array of numbers) . Since we have to repeat this for $$$O(n)$$$ steps, the total time complexity will be $$$\mathcal O(n^2 \cdot (\log n + U))$$$ and the memory complexity is $$$\mathcal O(n^2)$$$.