Product Minimize Mod

Input

The first line contains single integer $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n$ and $c$ $(1 \leq n \leq 2 \cdot 1 0^{5}, 1 \leq c \leq 20)$ (1 \le n \le 2 \cdot 10^5,\; 1 \le c \le 20).

The second line contains $n$ integers $(0 \leq l_{1}, l_{2}, \dots, l_{n} \leq 1 0^{9})$ (0 \le l_1, l_2, \dots, l_n \le 10^9).

The third line contains $n$ integers $(0 \leq r_{1}, r_{2}, \dots, r_{n} \leq 1 0^{9})$ (0 \le r_1, r_2, \dots, r_n \le 10^9).

It's guaranteed that $\sum n \leq 2 \cdot 1 0^{5}$ \sum n \le 2 \cdot 10^5 overall test cases.

Output

Print one line containing $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n — a valid array that minimizes the value of:

(i = 1 \prod n a_{i}) mod c

\left(\prod_{i=1}^{n} a_i\right) \bmod c

If multiple arrays satisfy the condition, print any of them.

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $10$ points) : $(l_{i} = r_{i})$ (l_i=r_i).
Subtask $2$ ( $10$ points) : $(n = 1)$ (n=1).
Subtsak $3$ ( $10$ points) : $(c = 2)$ (c=2)
Subtask $4$ ( $20$ points) : $(n, c \leq 8)$ (n,c \le 8)
Subtask $5$ ( $300$ points) : No additional constraints.