Trải qua kì thi quan trọng xong, Sắn về quê bắt tay làm kinh doanh với mảnh đất quê hương. Sắn bắt đầu làm nông trại với \(N\) chú bò sữa. Chú bò thứ \(i\) sản xuất \(a_i\) đơn vị sữa mỗi ngày.

Mỗi sáng sớm Sắn lùa lũ bò ra đồng cỏ để ăn những ngọn cỏ ngon nhất, tối Sắn lại lùa bò về chuồng. Lần này Sắn nâng cấp máy và mua thêm một máy nữa. Bây giờ Sắn có hai máy vắt sữa phục vụ để vắt hết \(N\) chú bò. Để đảm bảo công suất hoạt động của hai máy vắt sữa, mỗi lần vắt Sắn sẽ chia đều \(N\) chú bò vào hai máy sao cho lượng sữa hai máy vắt được tương đương nhau. Bạn hãy liệt kê cho Sắn biết tất cả cách sắp \(N\) chú bò vào hai máy để đạt được điều này.

Input

• Dòng thứ nhất chứa 1 số nguyên \(N\) \((1 \leq N \leq 20)\)
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots a_N (1 \leq a_i \leq 10^9)\), là sản lượng sữa của \(N\) chú bò.

Output

• Nếu không có cách nào thỏa mãn, hãy in ra \(-1\).
• Ngược lại hãy in ra mỗi đáp án trên 1 dòng riêng: Mỗi cách gồm \(N\) số nguyên \(x_1,x_2, \dots x_N, (x_i \in \{1,2\})\), là máy mà chú bò thứ \(i\) được phân vào. Các cách được in theo thứ tự từ điển.

Example

5
2 1 2 1 2 

11212
12122
12221
21112
21211
22121

5
2 1 2 1 8 

-1

5
1 5 1 3 4 

11122
22211