Question
ICPC Extension
In the ICPC Regionals, there are n students sitting in a row. Every student who has access to an extension cord is marked as 1, and every student without access is marked as 0. This information is stored as a binary string s of length n.
Some students are unhappy with this socket distribution, so the contest coordinator comes up with a unique idea: there will be k rounds of operations during the contest considering the string s as 1-indexed.
For the j-th round (1 ≤ j ≤ k):
-
For every index
i(1 ≤ i ≤ n) such thatiis divisible byj, the character at positioniin the string (after all previous operations) is toggled (0 → 1or1 → 0).
Your task is to return the final string after k rounds.
Input
The first line of each test case contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the size of the string and the number of rounds.
The second line of each test case contains a binary string of length KaTeX can only parse string typed expression, representing the initial state of students.
The second line of each test case contains a binary string of length KaTeX can only parse string typed expression, representing the initial state of students.
Output
Print the final binary string after KaTeX can only parse string typed expression rounds.
Example
Input
5 2
11111
Output
01010
Explanation
Initial string = 11111
For 1st Round: KaTeX can only parse string typed expression: All positions (1, 2, 3, 4, 5) are divisible by 1 → toggled → 00000
For 2nd Round: KaTeX can only parse string typed expression: Positions (2, 4) are divisible by 2 → toggled → 01010
Final string = 01010.
5 2
11111
Output
01010
Explanation
Initial string = 11111
For 1st Round: KaTeX can only parse string typed expression: All positions (1, 2, 3, 4, 5) are divisible by 1 → toggled → 00000
For 2nd Round: KaTeX can only parse string typed expression: Positions (2, 4) are divisible by 2 → toggled → 01010
Final string = 01010.