У AquaMoon есть строка \(a\), состоящая только из \(0\) и \(1\). Она хочет добавить \(+\) и \(-\) между всеми парами соседних позиций, чтобы абсолютное значение полученного выражения было как можно меньше. Можете ли вы ей помочь?
Первая строка содержит одно целое число \(t\) (\(1 \leq t \leq 2\,000\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2 \leq n \leq 100\)) — длину \(a\).
Вторая строка каждого набора входных данных содержит строку \(a\) длины \(n\), состоящую только из \(0\) и \(1\).
Для каждого набора входных данных выведите в отдельной строке строку длины \(n - 1\), состоящую из \(-\) и \(+\). Если существует более одного способа расстановки знаков, дающего наименьшее возможное абсолютное значение, то принимается любой из них.
В первом наборе входных данных мы можем получить выражение \(1 - 1 = 0\), с абсолютным значением \(0\).
Во втором наборе входных данных мы можем получить выражение \(0 + 1 - 1 + 0 + 1 = 1\), с абсолютным значением \(1\).
В третьем наборе входных данных мы можем получить выражение \(1 + 0 + 0 + 0 - 1 = 0\), с абсолютным значением \(0\).
3 2 11 5 01101 5 10001
- +-++ +++-
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач