这是问题的困难版本。版本之间的区别在于,硬版本确实需要您输出要移除的杆的数量。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
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$$$) - 杆数和问题数。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的非空字符串 $$$s$$$,其中,如果 $$$s_i$$$ 是“+”符号,则第 $$$i$$$ 杆的电荷为 $$$1$$$,如果 $$$s_i$$$ 是“-”符号,则 $$$-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$$$ 数字,并用空格分隔 - 要移除的杆数。
如果有多个正确答案,您可以打印任何一个。
示例
输入 #1
3 14 1 +--++---++-++- 1 14 14 3 +--++---+++--- 1 14 6 12 3 10 4 10 +-+- 1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4
输出 #1
2 5 8 2 1 11 1 9 0 1 1 2 1 2 1 2 2 1 3 1 2 2 2 3 1 3 1 3 2 3 4 1 4
注意
在第一个查询的第一个测试用例中,您可以删除编号为 $$$5$$$ 和 $$$8$$$ 的杆,然后将保留以下一组杆:+--+--++-++-。很容易看出这里符号变量和为零。
在第二个测试用例中:
- 对于第一个查询,我们可以删除编号为 $$$1$$$ 和 $$$11$$$ 的棒,然后将保留以下一组棒:--++---++---。很容易看出这里符号变量和为零。
- 对于第二个查询,我们可以删除编号为 $$$9$$$ 的杆,然后将保留以下一组杆:---++-。很容易看出这里变量 sum 为零。
- 对于第三个查询,我们根本无法移除杆。