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.

2 13
1 2 3 4
6

0110

2 7
3 2 3 3
2

0011