I2. Инверсия пар (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничение на число 1 в финальной строке более строгое. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Вам дана бинарная строка $$$s_1s_2\ldots s_n$$$, содержащая только символы 0 и 1. Вы можете выполнить $$$\lfloor\frac{n}{2}\rfloor$$$ операций. На $$$x$$$-й операции вы можете выполнить следующее:

  • Выберите целое число $$$l$$$ такое, что $$$0 \leq l \leq n-x$$$. Если $$$l=0$$$, то ничего не происходит. В противном случае символы $$$s_l$$$ и $$$s_{l+x}$$$ оба инвертируются. То есть, для каждого символа, если он равен $$$0$$$, то он меняется на $$$1$$$, и наоборот.

Ваша задача состоит в том, чтобы найти серию операций, чтобы количество оставшихся 1 в бинарной строке было не более $$$7$$$. Можно показать, что при данных ограничениях в задаче это всегда возможно.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \leq n \leq 2\cdot 10^6$$$).

Вторая строка каждого набора входных данных содержит бинарную строку $$$s_1s_2\ldots s_n$$$ ($$$s_i \in \{0,1\}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^6$$$.

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

Для каждого набора входных данных выведите строку из $$$\lfloor\frac{n}{2}\rfloor$$$ чисел: выбранные $$$l$$$ для операций $$$1,2,\ldots,\lfloor\frac{n}{2}\rfloor (0 \leq l_x \leq n-x)$$$. Вы должны гарантировать, что после всех операций в строке останется не более $$$7$$$ символов 1.

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

Пример
Входные данные
6
3
000
4
1101
5
11101
9
111111111
10
1111111011
15
110011101010100
Выходные данные
0 
1 1
1 3 
6 2 0 2 
1 0 0 0 0
13 6 8 5 2 8 1
Примечание

В четвертом наборе входных данных:

  • Изначально, $$$s=$$$111111111. Поскольку $$$n=9$$$, мы выполняем $$$\lfloor\frac{9}{2}\rfloor=4$$$ операции.
  • Первая операция имеет $$$l=6$$$. Поэтому символы $$$6$$$ и $$$6+1=7$$$ инвертируются. Теперь $$$s=$$$111110011.
  • Вторая операция имеет $$$l=2$$$. Поэтому символы $$$2$$$ и $$$2+2=4$$$ инвертируются. Теперь $$$s=$$$101010011.
  • Третья операция имеет $$$l=0$$$. Поэтому ничего не происходит.
  • Четвертая операция имеет $$$l=2$$$. Поэтому символы $$$2$$$ и $$$2+4=6$$$ инвертируются. Теперь $$$s=$$$111011011.
  • Поскольку в финальной строке $$$7$$$ символов 1 и $$$7 \leq 7$$$, это решение верно.