보간

제갈킨 다항식(Zhegalkin polynomial)은 다음과 같이 표현되는 불리언 함수 $f(x_1,\dots,x_n)$이다.

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

여기서 $\oplus$와 $\wedge$는 각각 XOR과 AND 불리언 연산을 나타내며, XOR은 모든 변수 부분집합에 대해 취해지고, $\{1, 2, \ldots, n\}$의 각 부분집합 $S$에 대해 $a_S \in \{0, 1\}$이다.

이 문제에서는 $m$개의 변수 값 집합 $({v_i}_{1},\dots,{v_i}_{n})$과 $m$개의 불리언 값 $y_i \in \{0, 1\}$이 주어진다. 각 $i = 1, 2, \ldots, m$에 대해 $f({v_i}_{1},\dots,{v_i}_{n}) = y_i$를 만족하는, 0이 아닌 항이 최대 $9000$개인 제갈킨 다항식을 구성해야 한다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. 이는 변수의 개수와 주어지는 변수 값의 개수이다 ($1 \leq n, m \leq 2000$).

다음 $m$개의 줄 각각에는 $i$번째 변수 값 집합을 나타내는 길이 $n$의 문자열($0$ 또는 $1$)과 정수 $y_i$가 주어진다.

모든 변수 값 집합은 서로 다르며, 적어도 하나의 집합에 대해 $y_i=1$임이 보장된다.

다항식은 $a_S = 1$인 항을 최대 $9000$개 포함해야 한다. 그러한 각 항에 대해, 대응하는 변수 부분집합 $S$를 길이 $n$의 문자열($0$ 또는 $1$)로 출력한다. $i$번째 문자가 $1$이면 $i \in S$이고, $0$이면 $i \notin S$이다. 항은 임의의 순서로 출력해도 되지만, 중복된 부분집합이 있어서는 안 된다.

가능한 답이 여러 개라면 그중 아무거나 출력한다. 해가 존재하지 않으면 $-1$을 출력한다.

해가 존재한다면, $a_S = 1$인 항 $S$가 최대 $9000$개인 해도 존재함이 보장된다.

첫 번째 예제의 가능한 답 중 하나는 $f(x_1,x_2)=1$이다.

두 번째 예제에서 $f(x_1,x_2,x_3)=x_1\oplus x_2\oplus x_3$는 가능한 답 중 하나이다.