F - XOR Table
Practice
4 (32 votes)
Approved
Easy Medium
Problem
60% Success 1271 Attempts 30 Points 6s Time Limit 256MB Memory 1024 KB Max Code

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

Extra constraints Points Which tests
\(N \le 10\) 10 1
\(M \le 10\) 20 2
\(M \le 50\,000\) 30 3
no extra constraints 40 4

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
525 votes
Tags:
ReadyHiringBITApprovedEasy-Medium
Points:30
Tags:
Medium
Points:30
Tags:
Easy-Medium