vp

Initially, Andrei had two sequences $V$ and $P$ of $N$ elements each. The sequence $V$ contained natural numbers $< M$, while the sequence $P$ had numbers with the following property: $P_i = (P_{i-1} \times V_i) \ (\text{mod} \ M)$ for each $i$, $2 \leq i \leq N$, and $P_1 = V_1$.

One morning, Andrei realized that some numbers had been smudged and were unreadable!

Since Andrei wants both sequences $V$ and $P$ to be readable from the beginning to the end, he asks you to help him reconstruct the sequences.

Input data

The first line contains $2$ natural numbers $N$ and $M$, and the second and third lines of the input contain the sequences $V$ and $P$, respectively. If a number at position $i$ is $-1$, it means that number is unreadable. It is guaranteed that the readable numbers respect the given property.

Output data

The first line will contain the readable sequence $V$ from start to finish, and the second line will contain the readable sequence $P$ from start to finish. Since Andrei is a thoughtful boy, he will accept any solution you find, as long as it respects the rule of the sequences.

Constraints and clarifications

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 1000$
• For $42$ points, $N \leq 1000$
• It is guaranteed that a solution exists
• During the contest "RoAlgo Contest #2", there was no test with id 14. It was added later so that only the solution with the best complexity would score 100 points

Example 1

stdin

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

stdout

1 4 4
1 4 4

Explanation

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

Therefore, these sequences respect the property.

Example 2

stdin

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

stdout

2 2 5
2 4 6

Explanation

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

Therefore, these sequences respect the property.