C. Дрим Тим
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп — менеджер проектов в IT-компании. В настоящий момент ему надо выбрать разработчиков себе в команду для старта нового проекта. Всего в компании есть $$$n$$$ разработчиков «на бенче» (то есть, незадействованных в других проектах). Поликарп оценил умение и навыки каждого из них: $$$a_i$$$ ($$$-10^4 \le a_i \le 10^4$$$) — целочисленная характеристика $$$i$$$-го разработчика. Эта величина может быть как положительной, так и нулевой и даже отрицательной (некоторые разработчики только учатся приносить пользу).

После того, как Поликарп выберет себе некоторое подмножество разработчиков в команду, сила команды будет определяться суммой величин $$$a_i$$$ по всем выбранным разработчикам.

Поликарп опасается, что если он выберет команду так, что максимизирует сумму характеристик $$$a_i$$$, то другие менеджеры могут найти это некрасивым. По этой причине он планирует собрать такую команду, что сумма значений $$$a_i$$$ для неё строго меньше максимальной возможной суммы.

Помогите Поликарпу выбрать любую такую команду, что:

  • сумма характеристик $$$a_i$$$ по всем членам выбранной команды строго меньше максимальной суммы, которую можно достичь, выбрав команду некоторым образом;
  • и одновременно сумма характеристик $$$a_i$$$ по всем членам выбранной команды максимально возможна.

Если в соответствии с требованиями выше выбрать команду можно несколькими способами, то достаточно найти любой из них.

Гарантируется, что сумма характеристик в искомой команде строго положительна, другими словами, Поликарп всегда сможет выбрать себе непустую команду.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество свободных разработчиков в компании.

Вторая строка содержит последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^4 \le a_i \le 10^4$$$) — характеристики $$$n$$$ разработчиков. Гарантируется, что характеристики таковы, что сумма характеристик в ответе строго положительна.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$10^5$$$.

Выходные данные

Выведите ответы для $$$t$$$ наборов входных данных в порядке их задания в тесте. В первую строку каждого ответа выведите положительное целое число $$$s$$$ — сумму характеристик в искомой команде. Вторая строка должна содержать только символы 0 и 1 и соответствовать искомой команде:

  • символ в $$$i$$$-й позиции должен быть равен 1, если $$$i$$$-й разработчик принадлежит команде;
  • символ в $$$i$$$-й позиции должен быть равен 0, если $$$i$$$-й разработчик не принадлежит команде.

Если ответов несколько, то выведите любой из них.

Пример
Входные данные
5
5
1 -1 1 -1 1
2
11 1
3
5 -3 4
3
5 3 -4
5
-1 0 3 -3 0
Выходные данные
2
11101
11
10
6
111
5
100
2
10100
Примечание

В первом наборе входных данных, максимальный поднабор $$$a_1, a_3, a_5$$$ имеет сумму равную $$$3$$$, поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).

Во втором наборе, максимальный поднабор $$$a_1, a_2$$$ имеет сумму равную $$$12$$$, поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).

В третьем наборе, максимальный поднабор $$$a_1, a_3$$$ имеет сумму равную $$$9$$$.

В четвертом наборе, максимальный поднабор $$$a_1, a_2$$$ имеет сумму равную $$$8$$$.

В пятом наборе, есть несколько поднаборов с максимальной суммой равной $$$3$$$, поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).