Problem11338--[yosupo] Linear Algebra - Matrix Product (Mod 2)

11338: [yosupo] Linear Algebra - Matrix Product (Mod 2)

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 512 MiB

Description

Given $N \times M$ matrix $A$ and $M \times K$ matrix $B$, print $C = AB \bmod 2$.

When dealing with matrix input and output, please treat each row as a string concatenated with its components ($0$ or $1$).

Input

$N\ M\ K$
$a_{11}a_{12} \cdots a_{1M}$
$a_{21}a_{22} \cdots a_{2M}$
$\vdots$
$a_{N1}a_{N2} \cdots a_{NM}$
$b_{11}b_{12} \cdots b_{1K}$
$b_{21}b_{22} \cdots b_{2K}$
$\vdots$
$b_{M1}b_{M2} \cdots b_{MK}$

Output

$c_{11}c_{12} \cdots c_{1K}$
$c_{21}c_{22} \cdots c_{2K}$
$\vdots$
$c_{N1}c_{N2} \cdots c_{NK}$

Constraints

- $1 \leq N,M,K \leq 2^{12}$
- $a_{ij},b_{ij} \in \lbrace 0,1\rbrace$

Sample 1 Input

2 2 2
11
10
10
11

Sample 1 Output

01
10

Sample 2 Input

1 2 3
10
101
010

Sample 2 Output

101

Sample 3 Input

1 1 1
0
0

Sample 3 Output

0

HINT

Source/Category