The DNA is very exciting,isn't it? A group of biologists tried their best to study DNA for an important project.Because of their hard work they found some rules about DNA.To their surprise the rules are very easy to understand:

There are only 2 mutations that may appear.Say S1,S2.And S1,S2 must be appeared in turn.Further more the period of S1 is A,the period of S2 is B.
If A=2,B=3,the mutations are appeared as follow:


            S1 S1 S2 S2 S2 S1 S1 S2 S2 S2 S1 S1 S2 S2 S2......
As you known,a DNA is a string of genes.Suppose the DNA contains N genes and each gene has 2 states,say alive and dead.For any mutation Sk(k=1,2),there is a table Gk,The jth number of the ith line of the table Gk is either 1 or 0 which indicates whether gene j has some effections on gene i or not.Suppose there are ci alive genes that can effect gene i.If ci is odd then after Si gene will be alive otherwise it will be dead.

Now the group want to know what is the state of each gene of a DNA after M mutations.As an ace programmer,they come to you for help.Can you help them?

Input:

The first line of each test case contains 4 integers: N (0<N<=50), M(0<=M<=2147483647), A(0<A<=2147483647), B(0<B<=2147483647), 0<A+B<=2147483647, which are described above. Then two N*N tables describe the G1 and G2. The last line of the test case is n strings either "alive" or "dead" which indicates the state of the N genes initially. There are several test cases and the input is terminated by EOF. 

Output:

For each test case,output a line of the state of each gene after M mutations.The state of the the N genes must be seperated by a space but no spaces at the end of line

Sample Input:
3 4 1 2
0 1 0
0 1 1
1 1 0
1 0 0
0 0 0
0 0 0
alive alive dead


Sample Output:
dead dead alive



Author: CAO, Peng