Məhsulun Modunu Minimuma Endirmək

Giriş

İlk sətirdə tək bir tam ədəd $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test halları sayını göstərir.

Hər bir test halının ilk sətirində iki tam ədəd $n$ və $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).

İkinci sətirdə $n$ tam ədəd $(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).

Üçüncü sətirdə $n$ tam ədəd $(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).

Ümumilikdə test halları üçün $\sum n \leq 2 \cdot 1 0^{5}$ \sum n \le 2 \cdot 10^5 olduğu təmin edilir.

Çıxış

Bir sətirdə $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n çap edin — aşağıdakı dəyəri minimuma endirən etibarlı bir massiv:

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

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

Əgər bir neçə massiv şərti ödəyirsə, onlardan istənilən birini çap edin.

Nümunələr

Nümunə 1

Loading

Bal hesablama

Alt vəzifə $1$ ( $10$ xal) : $(l_{i} = r_{i})$ (l_i=r_i).
Alt vəzifə $2$ ( $10$ xal) : $(n = 1)$ (n=1).
Alt vəzifə $3$ ( $10$ xal) : $(c = 2)$ (c=2)
Alt vəzifə $4$ ( $20$ xal) : $(n, c \leq 8)$ (n,c \le 8)
Alt vəzifə $5$ ( $300$ xal) : Əlavə məhdudiyyət yoxdur.