Поликарп — менеджер проектов в IT-компании. В настоящий момент ему надо выбрать разработчиков себе в команду для старта нового проекта. Всего в компании есть \(n\) разработчиков «на бенче» (то есть, незадействованных в других проектах). Поликарп оценил умение и навыки каждого из них: \(a_i\) (\(-10^4 \le a_i \le 10^4\)) — целочисленная характеристика \(i\)-го разработчика. Эта величина может быть как положительной, так и нулевой и даже отрицательной (некоторые разработчики только учатся приносить пользу).
После того, как Поликарп выберет себе некоторое подмножество разработчиков в команду, сила команды будет определяться суммой величин \(a_i\) по всем выбранным разработчикам.
Поликарп опасается, что если он выберет команду так, что максимизирует сумму характеристик \(a_i\), то другие менеджеры могут найти это некрасивым. По этой причине он планирует собрать такую команду, что сумма значений \(a_i\) для неё строго меньше максимальной возможной суммы.
Помогите Поликарпу выбрать любую такую команду, что:
- сумма характеристик \(a_i\) по всем членам выбранной команды строго меньше максимальной суммы, которую можно достичь, выбрав команду некоторым образом;
- и одновременно сумма характеристик \(a_i\) по всем членам выбранной команды максимально возможна.
Если в соответствии с требованиями выше выбрать команду можно несколькими способами, то достаточно найти любой из них.
Гарантируется, что сумма характеристик в искомой команде строго положительна, другими словами, Поликарп всегда сможет выбрать себе непустую команду.
Выходные данные
Выведите ответы для \(t\) наборов входных данных в порядке их задания в тесте. В первую строку каждого ответа выведите положительное целое число \(s\) — сумму характеристик в искомой команде. Вторая строка должна содержать только символы 0 и 1 и соответствовать искомой команде:
- символ в \(i\)-й позиции должен быть равен 1, если \(i\)-й разработчик принадлежит команде;
- символ в \(i\)-й позиции должен быть равен 0, если \(i\)-й разработчик не принадлежит команде.
Если ответов несколько, то выведите любой из них.
Примечание
В первом наборе входных данных, максимальный поднабор \(a_1, a_3, a_5\) имеет сумму равную \(3\), поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).
Во втором наборе, максимальный поднабор \(a_1, a_2\) имеет сумму равную \(12\), поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).
В третьем наборе, максимальный поднабор \(a_1, a_3\) имеет сумму равную \(9\).
В четвертом наборе, максимальный поднабор \(a_1, a_2\) имеет сумму равную \(8\).
В пятом наборе, есть несколько поднаборов с максимальной суммой равной \(3\), поэтому Поликарп должен выбрать команду с меньшей суммой (но максимальной возможной).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|