연립 일차 방정식 (법 2)

$N \times M$ 행렬 $A$와 크기가 $N$인 벡터 $b$가 주어진다. $Ax = b$를 만족하는 크기 $M$의 벡터 $x$를 구한다. 모든 것은 $\mathbb{F}_{2}$에서 고려한다.

행렬과 벡터를 입력하고 출력할 때는 각 행을 그 성분들($0$ 또는 $1$)을 이어 붙인 문자열로 취급한다.

제약 조건

• $1 \leq N \leq 4096$
• $1 \leq M \leq 4096$
• $A_{ij} \in \lbrace 0,1\rbrace$
• $b_{i} \in \lbrace 0,1\rbrace$

$N$ $M$
$A_{0,0}A_{0,1}\cdots A_{0,M-1}$
$A_{1,0}A_{1,1}\cdots A_{1,M-1}$
$\vdots$
$A_{N-1,0}A_{N-1,1}\cdots A_{N-1,M-1}$
$b_0b_1\cdots b_{N-1}$

해가 없다면 다음을 출력한다.

-1

해가 존재한다면 다음과 같이 출력한다.

$R$
$c_0c_1\cdots c_{M-1}$
$d_{0,0}d_{0,1}\cdots d_{0,M-1}$
$\vdots$
$d_{R-1,0}d_{R-1,1}\cdots d_{R-1,M-1}$

$R$는 해의 랭크이다. $c_i$는 해 중 하나이다. 각 $j$에 대해, $d_{j,0}\cdots d_{j,M-1}$는 해의 기저이다.