CF1562D2 Two Hundred Twenty One (hard version)

这是该问题的困难版本。不同之处在于，困难版本要求你输出需要移除的杆的编号。只有在所有版本的问题都被解决后，你才能进行 hack。 Stitch 喜欢和他的朋友 Sparky 一起用不同的机器做实验。今天他们又造了一台新机器。 这台机器的主要元件是 $n$ 根沿一条直线排列、编号从 $1$ 到 $n$ 的杆。每根杆必须带有电荷，电荷的数值只能是 $1$ 或 $-1$（否则机器无法工作）。机器能正常工作的另一个条件是，所有杆的电荷的交错和必须为零。 更正式地说，这些杆可以表示为一个长度为 $n$ 的数组，每个元素为 $1$ 或 $-1$，并且必须满足条件：$a_1 - a_2 + a_3 - a_4 + \ldots = 0$，即 $$ \sum\limits_{i=1}^n (-1)^{i-1} \cdot a_i = 0 $$ Sparky 给所有 $n$ 根杆都充上了电，但不幸的是，杆的电荷并没有被正确设置（交错和不为零）。于是朋友们决定只保留部分杆。Sparky 有 $q$ 个问题。在第 $i$ 个问题中，Sparky 询问：如果机器只包含编号为 $l_i$ 到 $r_i$ 的杆，最少需要移除多少根杆才能使剩下的杆的交错和为零？同时 Sparky 还想知道这些被移除的杆的编号。如果交错和已经为零，则无需移除任何杆。 如果杆的数量为零，我们认为交错和为零，即总可以移除所有杆。 请帮助你的朋友们，回答 Sparky 的所有问题！

每个测试包含多个测试用例。 第一行包含一个正整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个正整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$），分别表示杆的数量和问题的数量。 第二行包含一个非空字符串 $s$，长度为 $n$，其中第 $i$ 个字符为 "+" 表示第 $i$ 根杆的电荷为 $1$，为 "-" 表示电荷为 $-1$。 接下来的 $q$ 行，每行包含两个正整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），描述 Sparky 的问题。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$，$q$ 的总和不超过 $3 \cdot 10^5$。 保证所有测试用例中答案（最少需要移除的杆数）的总和不超过 $10^6$。

对于每个测试用例，按如下格式输出答案： 第一行输出一个整数 $k$，表示最少需要移除的杆数。 第二行输出 $k$ 个用空格分隔的整数，表示需要移除的杆的编号。 如果有多种正确答案，可以输出任意一种。

在第一个测试用例的第一个询问中，可以移除编号为 $5$ 和 $8$ 的杆，剩下的杆为：+--+--++-++-。可以很容易地验证，此时交错和为零。 在第二个测试用例中： - 对于第一个询问，可以移除编号为 $1$ 和 $11$ 的杆，剩下的杆为：--++---++---。可以很容易地验证，此时交错和为零。 - 对于第二个询问，可以移除编号为 $9$ 的杆，剩下的杆为：---++-。可以很容易地验证，此时交错和为零。 - 对于第三个询问，可以一个杆都不移除。 由 ChatGPT 4.1 翻译