time limit per test: 0.75 sec.
memory limit per test: 4096 KB

input: standard
output: standard

There is a row consist of N coins. Each coin lies heads up or tails up. There is also binary vector A with (K-1) dimensions.
We accomplish M operations with our coins row: we select some consecutive K coins, and apply to selected coins transformation X for Di times (i=1..M, where i is a number of operation)
The transformation X for given row C with length K means:
1. We shift the row C in one position to the left in a cyclic way.
2. Then we scan the row C from the first (leftmost) coin to (K-1)-th coin: if coin Ci lies tails up, and Ai=1, then we turn over coin Ck
Obviously, that for constant coins row with length K transformation X is fully determined by vector A. But vector A haven't given to you. You have results of transformation L rows with length K (row of coins before transformation, and row after transformation). It is guarantied that there is exactly one vector A satisfied all L conditions.
Your task is to reconstruct initial row by given row after all operations being accomplished.

There is four integer numbers in the first line of input: N, M, K, L (2<=N<=50, 1<=M<=10, 1<=L<=200, 2<=K<=N).
Second line contains description of accomplished operations, M pairs of positive integer numbers Si and Di. Si is a starting point of selected coins subrow, Di is a number of iterations of transformation (Si <= N-K+1; Di <= 10^6).
There are the following L conditions determining transformation X, L blocks by two lines each: first line of each block contains a row before transformation, and the second line contains row after transformation. Each line consists of K symbols, 1 denotes tails, 0 denotes heads.
The last line contains N symbols - row of coins after all operations accomplished. i-th symbol is 1 if i-th coin lies tails up, and 0 otherwise.

Write N symbols in single line of output: i-th symbol must be 1 if i-th coin of initial row laid tails up, and 0 otherwise.

Input

4 2 3 2
2 1 1 1
010
101
101
011
1010