GrayInc#786

GrayInc

1 second

64 megabytes

Hard

Gray Inc. is a software manufacturer specialized in the management of Gray codes. An $n$ -binary code, for $n \geq 1$ n \geq 1, is a sequence of words $w_{0}, w_{1}, \dots$ w_0, w_1, \ldots that includes every possible binary word of $n$ bits. An $n$ -Gray code is an $n$ -binary code such that between any two consecutive words there is only one bit that changes, i.e., they differ at exactly one position. As you might be aware, there are many $n$ -Gray codes.

Gray Inc. produces its own particular kind of Gray code in the following way (name $G_{n}$ G_n the produced $n$ -Gray code, $n \geq 1$ n \geq 1):

The notation defining $G_{n}$ G_n should be understood as follows:

$b A$ : appends bit $b$ to every element of the sequence $A$ ;
$A B$ : concatenates sequences $A$ and $B$ ;
$A^{R}$ A^R : sequence with the elements of sequence $A$ in reversed order.

For instance,

and

Observe that not only $G_{n}$ G_n is an $n$ -Gray code, but also a circular Gray code, as the first word in the sequence may be regarded as the successor of the last one in the sequence.

Gray Inc. wants your help to solve the following problem: given a binary word $w$ in $G_{n}$ G_n and a natural number $m$ , they want to produce the binary word in the sequence $G_{n}$ G_n that is $m$ words after $w$ in the listing (of course, considering the circular ordering described above). Can you help them?

Input

The problem input consists of several cases, each one defined by a line with an integer $m$ ( $0 < m \leq 1000$ 0 < m \leq 1000), and a binary $n$ -word $w$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100), separated by one blank.

The end of the input is given by a line with $m = 0$ m = 0 and $w = 0$ w = 0.

Output

For each input case, your solution should output the $n$ -binary word that is $m$ words after $w$ in the listing of $G_{n}$ G_n.

Examples

Example 1

Loading

n \geq 1

w_{0}, w_{1}, \dots

G_{n}

n \geq 1

G_{n}

A^{R}

G_{n}

G_{n}

G_{n}

0 < m \leq 1000

1 \leq n \leq 100

m = 0

w = 0

G_{n}