Hàm ~KMP()~ của một xâu ~S~ độ dài ~N~ kí tự (đánh số bắt đầu từ ~1~) được định nghĩa:

• ~KMP(I) = Max(L)~ thỏa đẳng thức ~\left(\left(S[1..L] = S[I-L+1..I] \text{ và } L < I\right) \text{ hoặc } L = 0\right)~.

Với:

• ~I, J~ là các số số tự nhiên từ ~1~ đến ~N~;
• ~S[I]~ là phần tử thứ ~I~ của xâu ~S~ khi viết ~S~ từ trái sang phải;
• Nếu ~I \leq J~ thì ~S[I..J] = S[I] + S[I+1] + ... + S[J-1] + S[J]~ (phép cộng chuỗi).

Một xâu ~S~ xác định chỉ có một hàm ~KMP()~ tương ứng duy nhất.

Cho trước một hàm ~KMP()~ đã xác định, hãy tìm một xâu thập lục phân ~S~ (chỉ gồm các kí tự ~0..9~ và ~A..F~) tương ứng.

Input

• Dòng đầu tiên: số nguyên ~N~ ~\left(1 \leq N \leq 100000\right)~.
• Dòng thứ hai: gồm ~N~ số nguyên biểu diễn một hàm ~KMP()~.

Output

• Một dòng duy nhất là xâu ~S~ có hàm ~KMP()~ tương ứng trùng với input.
• Nếu có nhiều xâu, hãy in ra xâu có thứ tự từ điển nhỏ nhất (qui định ~0 < 1 < 2 < \ldots < 9 < A < \ldots < F~).
• Nếu không tồn tại xâu ~S~, xuất ra ~-1~.

Sample Input 1

11
0 0 0 0 1 2 3 0 0 1 2

Sample Output 1

01110112101

Sample Input 2

7
0 0 1 2 3 4 4

Sample Output 2

-1