D. Breezy GCD Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ intervals $$$[l_i,r_i]$$$, where $$$l_i \le r_i$$$. Your task is to determine if there exist $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ satisfying:

  • $$$l_i\le x_i \le r_i$$$ for all $$$1 \le i \le n$$$;
  • $$$\operatorname{gcd}(x_1,x_2,\ldots,x_n) \neq 1$$$.
Here, $$$\operatorname{gcd}(x_1,x_2,\ldots,x_n)$$$ denotes the greatest common divisor of $$$x_1,x_2,\ldots,x_n$$$.
Input

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 an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) denoting the number of intervals.
  • The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 10^6$$$).
  • The third line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \le r_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output:

  • YES if it is possible to choose $$$x_1,x_2,\ldots,x_n$$$ such that it satisfies the constraints. On the next line, output $$$n$$$ space-separated integers $$$x_1,x_2,\ldots,x_n$$$.
  • NO otherwise.

The letters in the word YES and NO are case insensitive. For example, YES, yeS and No are all considered valid.

Example
Input
4
3
1 5 10
5 6 11
4
2 3 4 1000000
2 3 4 1000000
5
34 15 55 233 51
34 20 99 299 51
3
1 1 1
1 1 2
Output
YES
5 5 10
NO
YES
34 17 85 255 51
NO
Note

In the first example, we choose $$$5$$$, $$$5$$$ and $$$10$$$ respectively from each range. Then, we have $$$\operatorname{gcd}(5,5,10) = 5 \neq 1$$$.

In the second example, it is not possible to choose $$$n$$$ integers satisfying the condition.