Problem B
Array Shifting
Alice had an array $a$ of $n$ integers, each between $0$ and $2$, written at the top of her page.
Then, $k$ times, she performed the following operation: shift the array one position to the left (that is, delete the leftmost element), fill the vacated position at the end with $0$, and write the resulting array below the previous one.
Finally, she multiplied the numbers in each column to obtain a new array $b$ of length $n$, and memorized it. To keep the numbers small enough to remember, she computed all products modulo $10^9 + 7$.
Unfortunately, the original paper containing the sequence $a$ was lost in a fire. Given $b$, recover any array $a$ that could have produced the given $b$, or determine that it is impossible.
Input
The first line contains two integers $n$ and $k$ ($1 \le n \le 200{,}000$, $0 \le k < n$) — the length of the array and the number of operations.
The second line contains $n$ integers $b_1, b_2, \ldots , b_n$ ($0 \le b_i < 10^9 + 7$).
Output
If it is impossible to reconstruct such an array $a$, output:
\[ -1 \]Otherwise, output a single line with $n$ integers $a_1, a_2, \ldots , a_n$ ($0 \le a_i \le 2$) representing any valid array $a$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 2 2 4 4 0 0 |
2 1 1 2 2 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 2 1 1 5 0 0 0 |
-1 |
