18974번 - Interpolate 스페셜 저지다국어

문제

A Zhegalkin polynomial is a boolean function $f(x_1,\dots,x_n)$ which is represented as follows:

\[f(x_{1},\dots,x_{n}) = \bigoplus_{S \subseteq \{1, 2, \ldots, n\}} a_S \cdot \bigwedge_{i \in S} x_i,\]

where $\oplus$ and $\wedge$ stand for XOR and AND boolean operations respectively, XOR is taken over all subsets of variables, and $a_S \in \{0, 1\}$ for each subset $S$ of $\{1, 2, \ldots, n\}$.

In this task you are given $m$ sets of variable values $({v_i}_{1},\dots,{v_i}_{n})$ and $m$ boolean values $y_i \in \{0, 1\}$. You have to construct a Zhegalkin polynomial with at most 9000ドル$ non-zero terms satisfying $f({v_i}_{1},\dots,{v_i}_{n}) = y_i$ for each $i = 1, 2, \ldots, m$.

입력

The first line contains two integers $n$ and $m$ --- the number of variables and the number of given variable values (1ドル \leq n, m \leq 2000$).

Each of the following $m$ lines contains a string of $n$ characters 0ドル$ or 1ドル$ representing the $i$-th set of variable values, followed by the integer $y_i$.

It is guaranteed that all sets of variable values are distinct and $y_i=1$ for at least one set.

출력

Your polynomial has to contain at most 9000ドル$ terms having $a_S = 1$. For each such term print its corresponding subset $S$ of variables as a string of $n$ characters 0ドル$ or 1ドル$ such that $i$-th character equals 1ドル$ if $i \in S$ and 0ドル$ otherwise. You can output the terms in any order but there should be no repeating subsets.

If there are multiple possible answers, output any of them. If the solution does not exist, output $-1$.

It is guaranteed that if the solution exists, then the solution with at most 9000ドル$ terms $S$ having $a_S = 1$ exists as well.

제한

힌트

One of the possible answers to the first sample is $f(x_1,x_2)=1$.

In the second sample $f(x_1,x_2,x_3)=x_1\oplus x_2\oplus x_3$ is one of the possible answers.