Chia bò vào hai máy

Trải qua kỳ thi quan trọng, Quân trở về quê bắt tay vào làm kinh tế với mảnh đất quê hương. Quân bắt đầu với một nông trại có \(N\) chú bò sữa. Chú bò thứ \(i\) mỗi ngày sản xuất được \(a_i\) đơn vị sữa.

Hiện tại, Quân đã trang bị hai máy vắt sữa. Mỗi ngày, Sắn cần chia \(N\) chú bò vào hai máy sao cho:

• Mỗi chú bò chỉ được giao cho đúng một máy.
• Tổng lượng sữa được vắt từ mỗi máy là bằng nhau.

Hãy liệt kê tất cả các cách chia \(N\) chú bò vào hai máy sao cho thỏa mãn điều kiện trên.

Input

Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 20)\) --- số lượng chú bò.

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)\) --- sản lượng sữa mỗi ngày của từng chú bò.

Output

Nếu không tồn tại cách chia nào thỏa mãn, in ra -1.

Ngược lại, với mỗi cách chia thỏa mãn, in ra một dòng gồm \(N\) số nguyên \(x_1, x_2, \dots, x_N\) với \(x_i \in \{1,2\}\), biểu thị chú bò thứ \(i\) được gán cho máy số nào.

Các cách chia được in theo thứ tự từ điển tăng dầ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