CF2183I2.Pairs Flipping (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, the restriction on the number of 1's remaining in the final string is more strict. You can hack only if you solved all versions of this problem.

You are given a binary string $s_1s_2\ldots s_n$ containing only characters 0 and 1. You may perform $\lfloor\frac{n}{2}\rfloor$ operations. On the $x$-th operation, you may perform the following:

• Select an integer $l$ such that $0 \leq l \leq n-x$. If $l=0$, then nothing is done. Otherwise, the characters $s_l$ and $s_{l+x}$ are both flipped. That is, for each character, if it is $0$, then it is changed to $1$, and vice versa.

Your task is to find a series of operations such that the number of 1's remaining in the binary string is at most $7$. It can be shown that under the constraints of this problem, this is always possible.

这是该问题的困难版本。两个版本的区别在于，本版本对最终字符串中剩余的 1 的数量限制更为严格。仅当您已解决该问题的所有版本时，才可进行 hack。

给定一个仅由字符 0 和 1 组成的二进制字符串 $s_1s_2\ldots s_n$。您可以执行 $\lfloor\frac{n}{2}\rfloor$ 次操作。在第 $x$ 次操作中，您可以执行以下操作：

• 选择一个整数 $l$，满足 $0 \leq l \leq n-x$。若 $l=0$，则不执行任何操作；否则，将字符 $s_l$ 和 $s_{l+x}$ 同时翻转（即：若某字符为 0，则变为 1；若为 1，则变为 0）。

您的任务是找出一系列操作，使得二进制字符串中剩余的 1 的个数至多为 $7$。可以证明，在本题的约束条件下，这样的操作序列总是存在的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 2\cdot 10^6$).

The second line of each test case contains a binary string $s_1s_2\ldots s_n$ ($s_i \in {0,1}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2\cdot 10^6$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s_1s_2\ldots s_n$（其中 $s_i \in \{0,1\}$）。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^6$。

For each test case, output $\lfloor\frac{n}{2}\rfloor$ numbers on a new line: the chosen $l$ for operation $1,2,\ldots,\lfloor\frac{n}{2}\rfloor (0 \leq l_x \leq n-x)$. You should guarantee that after all operations, there are at most $7$ 1 remaining in the string.

If there are multiple solutions, output any.

对于每个测试用例，在新的一行输出 $\lfloor\frac{n}{2}\rfloor$ 个数字：依次为操作 $1,2,\ldots,\lfloor\frac{n}{2}\rfloor$ 中所选的 $l$ 值（满足 $0 \leq l_x \leq n-x$）。你需要确保在所有操作执行完毕后，字符串中最多剩余 $7$ 个 1。

若存在多种解法，输出任意一种即可。

In the fourth test case:

• Initially, $s=$111111111. Since $n=9$, we perform $\lfloor\frac{9}{2}\rfloor=4$ operations.
• The first operation has $l=6$. Therefore, characters $6$ and $6+1=7$ are flipped. Now, $s=$111110011.
• The second operation has $l=2$. Therefore, characters $2$ and $2+2=4$ are flipped. Now, $s=$101010011.
• The third operation has $l=0$. Therefore, nothing is done.
• The fourth operation has $l=2$. Therefore, characters $2$ and $2+4=6$ are flipped. Now, $s=$111011011.
• Since the final string has $7$ 1's and $7 \leq 7$, this solution is correct.

在第四个测试用例中：

• 初始时，$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$，该解法正确。