vp

Initial, Andrei avea doua șiruri $V$ și $P$ de $N$ elemente. Pe șirul $V$ erau puse niște numere naturale $< M$, dar pe șirul $P$ erau puse niște numere cu următoarea proprietate: $P_i = (P_{i-1} \times V_i)$ (mod $M$), pentru fiecare $i$, $2 \leq i \leq N$, iar $P_i=V_i$, pentru $i=1$.

Într-o dimineață, acesta realiza că a dat cu apă pe niște numere, și acestea erau necitibile!

Deoarece Andrei vrea ca ambele șiruri $V$ și $P$ să fie citibile cap-coadă, acesta vă roagă să îi reconstituiți șirurile.

Date de intrare

Pe prima linie se vor afla $2$ numere naturale $N$ și $M$, iar pe a doua și pe a treia linie din input, se vor găsi șirurile $V$, respectiv $P$. Dacă pe o poziție $i$ dată se află numărul $-1$, înseamnă că acest număr nu poate fi citibil. Se garantează că numerele citibile respectă proprietatea din enunț.

Date de ieșire

Pe prima linie se va afla șirul $V$ citibil cap-coadă, iar pe a doua linie se va afla șirul $P$ citibil cap-coadă. Deoarece Andrei este un băiat îngânduitor, acesta va permite orice soluție pe care ați găsit-o, dar trebuie să respecte regula șirurilor.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 1000$
• Pentru $42$ de puncte, $N \leq 1000$
• Se garantează că există soluție
• In timpul contestului "RoAlgo Contest #2", nu exista testul cu idul 14. Acesta a fost adaugat ulterior astfel incat doar solutia cu cea mai buna complexitate sa ia 100 de puncte

Exemplul 1

stdin

3 6
1 -1 4
-1 -1 -1

stdout

1 4 4
1 4 4

Explicație

• $1 = 1$
• $4 = (1 \times 4)$ (mod $6$)
• $4 = (4 \times 4)$ (mod $6$)

Deci șirurile acestea respectă proprietatea.

Exemplul 2

stdin

3 7
-1 -1 5
-1 -1 6

stdout

2 2 5
2 4 6

Explicație

• $2 = 2$
• $4 = (2 \times 2)$ (mod $7$)
• $6 = (4 \times 5)$ (mod $7$)

Deci șirurile acestea respectă proprietatea.