Hai máy vắt sữa

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Trang trại có hai máy vắt sữa. Mỗi con bò phải được đưa vào đúng một trong hai máy, và để hai máy chạy công suất như nhau, tổng lượng sữa của các con bò ở máy 1 phải bằng tổng lượng sữa của các con bò ở máy 2.

Một cách xếp là dãy \(x_1 x_2 \dots x_n\) với \(x_i \in \{1, 2\}\), trong đó \(x_i\) là số hiệu máy dành cho con bò thứ \(i\). Hãy liệt kê tất cả các cách xếp thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Nếu không có cách xếp nào, in ra -1.
• Ngược lại, mỗi dòng in một cách xếp dưới dạng xâu \(n\) chữ số \(x_1 x_2 \dots x_n\) viết liền nhau (không có dấu cách). Các cách xếp được in theo thứ tự từ điển tăng dần (so sánh như xâu ký tự).

Constraints

• \(1 \le n \le 20\)
• \(1 \le a_i \le 10^9\)

Sample Input

5
1 3 2 2 4

Sample Output

11122
11212
22121
22211

Explanation

Tổng sữa là \(12\), mỗi máy phải vắt được \(6\). Chẳng hạn cách 11122: máy 1 nhận các con \(1,2,3\) (\(1+3+2=6\)), máy 2 nhận các con \(4,5\) (\(2+4=6\)).