Problem

D(ZP,+,*) is an algebraic system, where

Suppose A, C ZP, if there exists a B ZP such that C = A * B, then we say A is a factor of C, denoted as A | C. If A | C, A | D, then A is a common factor of C and D. Furthermore, if A is a common factor of C, D and every common factor of C and D is also a factor of A, then A is said to be the greatest common factor of C and D.

Given C, D ZP, your task is to get their greatest common factor.

Input

The first line contains an integer T(T <= 100), which is the number of test cases. Each case will conform to the following form:

P m n

c0 c1 ... cm

d0 d1 ... dn

P is a prime number in the range of [2, 10000); 1 <= m, n <= 100; cm,dn > 0.

Output

For each test case, output coefficients of the greatest common factor in a single line in the following form:

a0 a1 ... ak

If the answer is not unique, you should print the one with ak = 1.

Sample Input

3
23 2 4
3 17 20
15 3 19 20 15
23 1 1
0 12
0 9
7 1 2
1 1
0 1 1

Sample Output

22 2 1
0 1
1 1


Author: wiltord