Главный секрет киноиндустрии заключается в том, что известный фильм «Люси» основан на реальных событиях, а в главных ролях была именно Тётя Люсине. Спойлер: в конце фильма Люси(не) превращается в компьютер. Причём компьютер необычный, в нём есть информация про все секреты вселенной, но в виде бинарной строки. Эту бинарную строку вам и нужно расшифровать самым-самым естественным образом.
Дана бинарная строка \(s\). Необходимо разбить её на произвольное количество непересекающихся подстрок так, чтобы сумма двоичных чисел, образованных этими подстроками, была точной степенью двойки, либо сказать, что это невозможно. Каждый символ \(s\) должен принадлежать ровно одной подстроке из разбиения.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 10^5\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
В единственной строке каждого набора входных данных вводится бинарная строка \(s\) (\(1 \le |s| \le 10^6\)).
Гарантируется, что сумма \(|s|\) по всем наборам входных данных не превосходит \(10^6\).
Для каждого набора входных данных выведите ответ на задачу следующим образом:
В первом наборе входных данных невозможно разбить строку так, чтобы получить степень двойки.
Во втором наборе входных данных возможно следующее разбиение:
4 00000 01101 0111011001011 000111100111110
-1 3 1 3 4 4 5 5 8 1 2 3 3 4 4 5 6 7 7 8 10 11 12 13 13 5 1 5 6 7 8 11 12 14 15 15
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач