A. The Binary Chicken Farm
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the most peculiar farm in the digital world - the Binary Chicken Farm! Here, the chickens don't just lay eggs; they lay binary eggs. Each egg contains a sequence of 0s and 1s, and the farm's success depends on properly managing these binary-laying hens.

The Binary Chicken Farm has N chickens, numbered from 1 to N. Each chicken lays exactly one binary egg per day. The egg from the i-th chicken on day j is represented by a binary string (e.g. 0101).

The farm owner has noticed a strange pattern: some chickens seem to influence others. Specifically, if chicken A influences chicken B, then the egg laid by chicken B on any given day will always be the binary XOR of its own previous day's egg and chicken A's previous day's egg. Otherwise, the chicken lays the same egg as in previous day.

Given the eggs laid on day 1 and the influence relationships between chickens, your task is to predict the eggs that will be laid on day K. Note that each chicken can be influenced only by one other chicken.

Input

The first line contains three space-separated integers:

- N: the number of chickens

- M: the number of influence relationships

- K: the day for which you need to predict the eggs

The second line contains N space-separated binary strings, each of length L, representing the eggs laid by each chicken on day 1.

The next M lines each contain two space-separated integers A and B, indicating that chicken A influences chicken B.

Output

Output N space-separated binary strings, each of length L, representing the eggs laid by each chicken on day K.

Example
Input
3 2 3
101 010 111
1 2
2 3
Output
101 010 010
Note

Limits

- 1 $$$\le$$$ N $$$\le$$$ 1000

- 0 $$$\le$$$ M $$$\le$$$ N

- 2 $$$\le$$$ K $$$\le$$$ $$$10^4$$$

- 1 $$$\le$$$ L $$$\le$$$ 20

- 1 $$$\le$$$ A, B $$$\le$$$ N

- A $$$\ne$$$ B