___________________________________________________________________ the solution is yet to be found [Qəpik]
You are given an array $A$ of positive integers and a set $S$ of prime numbers. You have to make the array $A$ beautiful after applying the following operation any number of times:
The array is beautiful if there exist at least $\lceil n / 2 \rceil$ beautiful elements. An element $x \in A$ is called beautiful if there exist an element $y \in A$ such that $y > x$ and $gcd(x, y) = x.$ Here $gcd(a, b)$ denotes the greatest common divisor of $a$ and $b.$
Can you make the array $A$ beautiful after applying the following operation any number of times.
The first line contains $T$ the number of test cases $(1 \leq T \leq 10^5)$. For each test cases:
The first line contains two integer $n$ and $m$ $(1 \leq n, m \leq 10^5)$ — the size of array $A$ and the size of set $S$ respectively.
The second line contains $n$ positive integers $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10^6)$ — the elements of $A$.
The third line contains $m$ distinct prime numbers $p_1, p_2, …, p_n$ $(1 \leq p_i \leq 10^6)$ — the elements of $S$.
It is guaranteed that, over all test cases $\sum n \leq 10^5$ and $\sum m \leq 10^5$.
If it is possible to make the array beautiful, print “Yes”, otherwise print “Roses”.
Input | Output |
---|---|
3 3 1 1 9 9 3 2 1 5 5 7 2 1 5 10 7 | Yes Roses Yes |
In the first test case, you can change one of the 9 to 1 dividing it by 3 two times. Thus final array is (1, 1, 9) which is a beautiful array. In the second test case, there is no way to make the array beautiful. In the third test case, the initial array is beautiful. |