You are given N numbers: d[0], d[1], ..., d[N - 1].

Output a string of bits with N bits (0/1) in which the i-th bit is 1 if there is any number before d[i] which equals d[i], otherwise output 0.

Then, output a string of bits with N bits (0/1) in which the i-th bit is 1 if there is any number after d[i] which equals d[i], otherwise output 0.



Input Format

N // count of the numbers in the input.

d[0] // 1st number

d[1] // 2nd number

...

d[n - 1] // last number

Output Format

The first line contains a string of n bits, where the i-th bit (as read left to right) indicates if there is any number before b[i] which is equal to b[i].

The second line contains a string of n bits, where the i-th bit (as read left to right) indicates if there is any number after b[i] which is equal to b[i].-You are given N numbers: d[0], d[1], ..., d[N - 1].

Output a string of bits with N bits (0/1) in which the i-th bit is 1 if there is any number before d[i] which equals d[i], otherwise output 0.

Then, output a string of bits with N bits (0/1) in which the i-th bit is 1 if there is any number after d[i] which equals d[i], otherwise output 0.



Input Format

N　　　 // count of the numbers in the input.

d[0]　 // 1st number

d[1]　 // 2nd number

...

d[n - 1] // last number

Output Format

The first line contains a string of n bits, where the i-th bit (as read　left to right) indicates if there is any number before b[i] which is equal to b[i].

The second line contains a string of n bits, where the i-th bit (as read　left to right) indicates if there is any number after b[i] which is equal to b[i].