Toggle Lights on a Circular Chandelier

Farmer John is displeased with the dim lighting on his farm and has just installed a beautifully decorated new chandelier. The chandelier consists of \(N\) (where \(3 \le N \le 16\)) lights arranged in a circle.

The cows have taken a keen interest in this luminous device and invented the following game:

At time \(T\), for each light \(i\) (with \(1 \le i \le N\)), if at time \(T-1\) the light immediately to its left was on, then the state of light \(i\) is toggled; otherwise, it remains unchanged. (Note that for light \(1\), its left neighbor is light \(N\).)

This operation is simultaneously applied to all lights and the process is repeated for \(B\) time units (where \(1 \le B \le 10^{15}\)). Note: \(B\) may exceed the range of a typical 32-bit integer.

Given the initial state of each light, compute the state of every light after \(B\) time units.

inputFormat

The input consists of two lines. The first line contains two integers \(N\) and \(B\): the number of lights and the number of time units, respectively.

The second line contains a string of \(N\) characters, each being either '0' or '1', representing the initial state of the lights (in order). A '1' indicates that a light is on, and a '0' indicates it is off.

outputFormat

Output a string of \(N\) characters representing the state of the lights after \(B\) time units. The \(i\)-th character should be '1' if the \(i\)-th light is on, and '0' otherwise.

sample

3 1
101

011