Мінімізація добутку за модулем

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість наборів тестових даних.

Перший рядок кожного набору тестових даних містить два цілі числа $n$ та $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).

Другий рядок містить $n$ цілих чисел $(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).

Третій рядок містить $n$ цілих чисел $(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).

Гарантується, що $\sum n \leq 2 \cdot 1 0^{5}$ \sum n \le 2 \cdot 10^5 для всіх наборів тестових даних.

Вихідні дані

Виведіть один рядок, що містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n — допустимий масив, який мінімізує значення:

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

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

Якщо кілька масивів задовольняють умові, виведіть будь-який з них.

Приклади

Приклад 1

Loading

Оцінювання

Підзадача $1$ ( $10$ балів) : $(l_{i} = r_{i})$ (l_i=r_i).
Підзадача $2$ ( $10$ балів) : $(n = 1)$ (n=1).
Підзадача $3$ ( $10$ балів) : $(c = 2)$ (c=2)
Підзадача $4$ ( $20$ балів) : $(n, c \leq 8)$ (n,c \le 8)
Підзадача $5$ ( $300$ балів) : Без додаткових обмежень.