Gray code

A binary number is a number in base $2$, where each digit, or bit, has a weight that is a power of $2$. For example, the decimal number $23$ is written $10111$ in binary because

$(1 \times 2^4) + (0 \times 2^3) + (1 \times 2^2) + (1 \times 2^1) + (1 \times 2^0) = 16 + 4 + 2 + 1 = 23$

A Gray code sequence is a sequence of binary values in which each value differs from its immediate predecessor in exactly one bit. The table below shows the standard Gray code sequence for 3-bit binary numbers.

Converting a binary number into its standard Gray code value takes a very simple algorithm. Say we convert the binary value $011$. Start by copying the first bit.

0 1 1
v
0

The second bit comes from adding the first and second bits of the given binary number, giving the sum $0 + 1 = 1$.

0 + 1 1
    v
0   1

The third bit comes from adding the second and third bits of the given binary number, giving the sum $1 + 1 = 10$ in binary. We discard the carry, so we take only the rightmost bit $0$ of the sum.

0 1 + 1
      v
0 1   0

The answer is therefore $010$.

In general, apart from the first bit, the $k$-th bit of the standard Gray code comes from adding the $(k-1)$-th bit and the $k$-th bit of the given binary number and discarding the carry. These four cases describe the carry-discarding addition completely.

  0    0    1    1
+ 0  + 1  + 0  + 1
---  ---  ---  ---
  0    1    1    0

Write a program that converts an $n$-bit binary value into its equivalent $n$-bit standard Gray code value, where $1 \le n \le 20$.

The input consists of two lines.

1. The first line contains the integer $n$, the number of bits, where $1 \le n \le 20$.
2. The second line contains a bit string of length $n$ representing the $n$-bit binary number.

Print a bit string of length $n$, the standard Gray code equivalent of the given $n$-bit binary number.