B. Breaking Bad
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a number $$$N$$$ of "legal" labs connected by bidirectional corridors, forming a connected graph. There are $$$M$$$ types of crystals. Every lab makes all types of crystals but specializes in some crystal types, as indicated by a binary string in the input. On day 0, lab $$$i$$$ owns $$$x_{ij}$$$ units of crystal type $$$j$$$.

Every night, all labs update their crystal inventories simultaneously. For a fixed crystal type $$$k$$$, lab $$$i$$$ performs the following process:

A "researcher" from the $$$i$$$ th lab will visit every other lab that can be reached through exactly $$$k$$$ corridors (he can use the same corridor multiple times along his path and it counts). For every possible lab $$$j$$$ that can be reached this way:

- If lab $$$j$$$ specializes in crystal $$$k$$$ and lab $$$i$$$ does not, lab $$$i$$$ gains $$$x_{jk}$$$ (lab $$$j$$$ is not affected).

- If lab $$$i$$$ specializes in crystal $$$k$$$ and lab $$$j$$$ does not, lab $$$i$$$ gains $$$x_{jk}$$$ (lab $$$j$$$ is not affected).

- Otherwise, nothing is gained.

The new amount of crystal $$$k$$$ in lab $$$i$$$ is: the old amount plus all the gained amounts.

All labs compute their new inventories using only the previous day's values.

Your task is to determine, on day $$$D$$$, whether each lab has an odd or even number of each crystal type.

Input

$$$N, M, D$$$ the number of labs, crystal types, and days, where $$$(1 \leq N \leq 200)$$$, $$$(1 \leq M \leq 50)$$$, and $$$(1 \leq D \leq 10^{18})$$$.

Next $$$N$$$ lines: A binary string $$$s_i$$$ of length $$$M$$$, where $$$s_{ik} = 1$$$ if lab $$$i$$$ specializes in crystal $$$k$$$, otherwise $$$0$$$.

Next $$$N$$$ lines: $$$M$$$ integers $$$x_{ik}$$$ per line: the initial crystal quantities for lab $$$i$$$ of crystal $$$k$$$, $$$(x_{ik} \leq 10^{18})$$$.

$$$E$$$ the number of corridors, where $$$0 \leq E \leq \frac{N(N-1)}{2}$$$.

Next $$$E$$$ lines: Two integers $$$u, v$$$ $$$(1 \leq u, v \leq N)$$$ denoting a bidirectional corridor between labs $$$u$$$ and $$$v$$$.

Output

Print $$$N$$$ lines. Each line contains $$$M$$$ values:

- $$$1$$$ if the amount of that crystal is odd on day $$$D$$$.

- $$$0$$$ if it is even.

Examples
Input
3 2 2
10
01
11
1 2
3 4
5 6
2
1 2
2 3
Output
1 0 
1 0 
1 0
Input
4 3 5
100
010
001
111
10 20 30
15 25 35
12 22 32
18 28 38
4
1 2
2 3
3 4
1 4
Output
0 0 0 
0 1 0 
0 0 0 
0 0 0