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 \le X \le 1$). The following equation holds for every $i, j$ that $0 \le i \le N - 2$, $0 \le j \le 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 \le T \le 8$
• $1 \le N \le 10^9$
• $2 \le M \le 10^6$
• $0 < P < M$
• $0 \le X \le 1$

Subtasks