Giải bài trực tuyến

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 ((S[1..L] = S[I-L+1..I] và L

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<=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' 'A'..'F') tương ứng.

Input

• Dòng đầu tiên: số nguyên N (1 <= N <= 100000);
• 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'<...<'9'<'A'<..<'F');
• Nếu không tồn tại xâu S, xuất ra -1;

Example

Input 1:
11
0 0 0 0 1 2 3 0 0 1 2

Output 1:
01110112101
 
Input 2:
7
0 0 1 2 3 4 4

Output 2:
-1