Remote Training on Programming

Имеется N камней разного веса.
Требуется разложить их на две кучки так, чтобы разница весов этих кучек была как можно меньше.

Input

В первой строке входного файла находится число N - количество камней (1<=N<=20).
В следующих строках располагаются N целых чисел - веса камней (в интервале от 1 до 10⁸). Числа разделяются пробелами и/или переводами строк.

Output

Выведите в первой строчке одно число - минимально возможный модуль разности весов кучек.
В следующей строчке выведите через пробел N чисел 1 или 2, где 1 означает, что соответствующий камень пойдёт в 1-ю кучу, 2 - во вторую. Если правильных решений несколько, выведите любое.

Sample

4
1 5 2 3

1
1 1 2 2