提示: 欢迎访问OurACM平台。
Problem 1069 Twinkling lights

Accept: 128    Submit: 406
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There is a ring consisting of n lights numbered as 1, 2, …,n (as shown in figure 1 ). At time 0, some lights are on and the others are off. At time t+1, light i alters its status (from on to off or from off to on), only if light i-1 is on at time t (for i=1, light i-1 means light n). Please work out the status of each light at time m.

Input

The first line of the input is an integer k denoting the number of test cases. The following 2k lines are input data. Each test case includes two lines. The first line consists of two integers separated by one space, where the first integer n (0<n<=10^4) denotes the number of lights and the second integer is m (0<m<=10^4). The second line is a binary string of length n, representing the status of each light in time 0 ( "1" denoting the light is on and "0" denoting the light is off ).

Output

For each test case, output a line containing a binary string representing the status of each light at time m.

Sample Input

2 5 3 00111 25 50 0100100100011101001100110

Sample Output

10001 1111110101111010111011111

Source

FJNUPC 2005

Submit  Back  Status  Discuss