Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

No tags yet

No tag edit access

time limit per test: 0.75 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard

output: 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.

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.

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

2 1 1 1

010

101

101

011

1010

Output

0110

Author: | Dmitry Orlov |

Resource: | Saratov ST team Spring Contest #1 |

Date: | 18.05.2003 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/27/2020 02:08:28 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|