Problem

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

• ZP = {a0 + a1x + a2x2 + ... anxn}, where n is a non-negative integer and ai (0 <= i <= n) is an integer, 0 <= ai < P, P is a prime number.
• If A, B ¡Ê ZP£¬A = a0 + a1x + a2x2 + ... amxm, B = b0 + b1x + b2x2 + ... bnxn; then
C = A + B = c0 + c1x + c2x2 + ... crxr, where r = max(m, n), ci = (ai+bi) mod P (0 <= i <= r);
D = A * B = d0 + d1x + d2x2 + ... dm+nxm+n, where di = (a0bi + a1bi-1 + ... + aib0) mod P.

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