f-xor-table

Let's consider a two-dimensional binary table A of N rows and M columns.
Let A_{i, j} denote a bit in the i-th row and j-th column.
Rows are numbered 0 through N-1 from top to bottom.
Columns are numbered 0 through M-1 from left to right.

You are given dimensions N, M, and the 0-th row of the table.
You are also given an integer P (0 < P < M) and a bit X (0 ≤ X ≤ 1).
The following equation holds for every i, j that 0 ≤ i ≤ N - 2, 0 ≤ j ≤ M-1:
$A_{i, j} \mathbin{\oplus} X = A_{i, (j + P) \% m} \mathbin{\oplus} A_{i + 1, (j + P) \% m}$
Here, \mathbin{\oplus} denotes the exclusive or logical operation. 

Your task is to find the (N - 1)-th row of the table.
If there are multiple correct answers, output any of them.
It can be proved that there exists at least one table satisfying the given conditions.

Input format
The first line of the input contains one integer T denoting the number of test cases.

The first line of each test case description contains four integers N, M, P and X.

The second line contains a binary string of M bits denoting the 0-th row of the table A.

Output format
For each test case, output a single line containing a binary string of M bits denoting the (N - 1)-th row of the table A. If there are multiple correct answers, output any of them.

Constraints

1 ≤ T ≤ 8
1 ≤ N ≤ 10^9
2 ≤ M ≤ 10^6
0 < P < M
0 ≤ X ≤ 1

SAMPLE INPUT
2
3 5 2 1
10111
10 10 1 0
1010001011

SAMPLE OUTPUT
00111
1011110111

Explanation

For the first test case of the sample input, the following table A satisfies the conditions given in the statement: 

10111
10101
00111

So, one of the possible outputs for this particular test case is 00111.

Stack Limit for C++ is 8MB. You are allowed to increase it in your code, e.g. using setrlimit().

Source: hackerearth | Difficulty: EASY


Solutions: