Limits 1s, 256 MB

___________________________________________________________________ the solution is yet to be found [Qəpik]

You are given an array AA of positive integers and a set SS of prime numbers. You have to make the array AA beautiful after applying the following operation any number of times:

  • Choose an integer ii (1in)(1 \leq i \leq n) and a prime pS.p \in S. Then perform Ai=Ai/p.A_i = A_i / p. Here pp must be a divisor of Ai.A_i.

The array is beautiful if there exist at least n/2\lceil n / 2 \rceil beautiful elements. An element xAx \in A is called beautiful if there exist an element yAy \in A such that y>xy > x and gcd(x,y)=x.gcd(x, y) = x. Here gcd(a,b)gcd(a, b) denotes the greatest common divisor of aa and b.b.

Can you make the array AA beautiful after applying the following operation any number of times.


The first line contains TT the number of test cases (1T105)(1 \leq T \leq 10^5). For each test cases:

The first line contains two integer nn and mm (1n,m105)(1 \leq n, m \leq 10^5) — the size of array AA and the size of set SS respectively.

The second line contains nn positive integers a1,a2,...,ana_1, a_2, ..., a_n (1ai106)(1 \leq a_i \leq 10^6) — the elements of AA.

The third line contains mm distinct prime numbers p1,p2,,pnp_1, p_2, …, p_n (1pi106)(1 \leq p_i \leq 10^6) — the elements of SS.

It is guaranteed that, over all test cases n105\sum n \leq 10^5 and m105\sum m \leq 10^5.


If it is possible to make the array beautiful, print “Yes”, otherwise print “Roses”.


3 1
1 9 9
2 1
5 5
2 1
5 10

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.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.