# Problem K

Knapsack 101

Everyone knows that the knapsack problem is NP-hard. That
is, everyone except for you! You are *not* convinced;
after all, you *know* that P = NP!

Your friend, determined you are wrong, challenges you to solve the following variant of the knapsack problem.

There are $2n$ items,
each with a weight $w_ i$.
Your task is to find a set of *exactly* $n$ *distinct* items such that
the product of their weights is equal to $z$ under modulo a prime $p$. In other words, you want to find
distinct indices $i_1, i_2,
\ldots , i_ n$ such that $w_{i_1} \times w_{i_2} \times \ldots \times
w_{i_ n} \equiv z \pmod{p}$.

Unfortunately for your friend, and fortunately for you, your
friend simply generates the weights of each item **uniformly and independently at random** from the
range $[1, p-1]$.
Furthermore, your friend generated $z$ by picking $n$ **random**
distinct indices $i_1, i_2,
\ldots , i_ n$ and computing $z \gets w_{i_1} \times w_{i_2} \times \ldots
\times w_{i_ n} \pmod{p}$. Prove your friend wrong by
solving this knapsack variant!

## Input

The first line contains two integers $n$ and $p$, denoting the number of items and the prime modulo respectively ($1 \leq n \leq 100\, 000$; $2 \leq p \leq 10^9$; $p$ is prime).

The next line contains $2n$ integers $w_1, w_2, \ldots , w_{2n}$, denoting
the weights of each item ($1 \leq
w_ i \leq p-1$). **It is guaranteed
that the weights of each item are generated uniformly and
independently at random from the range $[1, p-1]$**.

The next line contains an integer $z$, denoting the target value
($1 \leq z \leq p-1$).
**It is guaranteed that $z$ is generated by picking
$n$ random distinct
indices $i_1, i_2, \ldots , i_
n$ and computing $z \gets
w_{i_1} \times w_{i_2} \times \ldots \times w_{i_ n}
\pmod{p}$**. Therefore, a solution always exists.

## Output

Output a binary string of length $2n$. The $i$-th character of the string should
be `1` if you choose to include item
$i$ in your set, and
`0` otherwise. If there are multiple
solutions, you may output any of them. Note that there should
exactly be $n$ `1`’s in the binary string.

Sample Input 1 | Sample Output 1 |
---|---|

2 13 1 2 3 4 6 |
0110 |

Sample Input 2 | Sample Output 2 |
---|---|

2 7 3 2 3 3 2 |
0011 |