A Quad is a data container that consists of 4 bits, represented by a hexadecimal number. It has 2 halves - the upper half and the lower half.
Consider a binary number with digits B1,B2,B3,B4 where B1 is the most significant digit and B4 is the least significant digit. The upper half consists of bits B1 and B2, and the lower half consists of bits B3 and B4.
Upper half: ‫ B1 B2
Lower half: B3 B4
Multiple Quads are placed together, contiguously, from left to right.
Let the binary number formed by contiguously-placed upper halves of Quads be N1.
Let the binary number formed by contiguously-placed lower halves of Quads be N2.
For both N1 and N2, the rightmost digit is least significant and leftmost digit is most significant.
A QuadNumber is the sum of numbers N1 and N2.
If carry is obtained finally, it is to be ignored. Hence, print only 2*N least significant binary digits of the QuadNumber.
Given a set of contiguously placed Quads, find the QuadNumber (binary) formed by it.

Input
Input consists of 2 lines
The first line contains a single integer N, representing the number of digits in the Hexadecimal number.
The second line contains a contiguous set of Quads (hexadecimal numbers)
N
Q1 Q2 Q3 Q4 ... QN

Output
Print a single line containing the QuadNumber in binary.

Constraints

1 ≤ N ≤ 100000

Example
Input:
2
1A

Output:
1000

Input:
2
11

Output:
0101

见题面

见题面