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

Это сложная версия задачи. Различия между версиями заключаются в том, что в сложной версии требуется выводить номера удаляемых стержней. Вы можете делать взломы, только если обе версии задачи сданы.

Стич любит экспериментировать с различными механизмами вместе со своим другом Спарки. Сегодня они построили очередную машину.

Главным элементом этой машины являются $$$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$$$.

Спарки зарядил все $$$n$$$ стержней электрическим током, но оказалось, что стержни заряжены неправильно (знакопеременная сумма заряда не равна нулю). Друзья решили оставить в машине только часть стержней. У Спарки есть $$$q$$$ вопросов. В $$$i$$$-м вопросе Спарки интересуется: если бы машина состояла только из стержней с номерами с $$$l_i$$$ по $$$r_i$$$ включительно, какое минимальное количество стержней можно было бы удалить из машины так, чтобы знакопеременная сумма зарядов на оставшихся была равна нулю? Также Спарки хочет знать номера этих стержней. Возможно, друзья что-то напутали, и знакопеременная сумма уже равна нулю. В таком случае, можно не удалять стержни вовсе.

Если количество стержней равно нулю, будем считать, что знакопеременная сумма зарядов равна нулю, то есть всегда можно удалить все стержни.

Помогите друзьям и ответьте на все вопросы Спарки!

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

Каждый тест содержит несколько наборов входных данных.

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

В первой строке каждого набора входных данных находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — количество стержней и количество вопросов соответственно.

Во второй строке находятся строка $$$s$$$ длины $$$n$$$, где заряд $$$i$$$-го стержня равен $$$1$$$, если $$$s_i$$$ это символ «+», или $$$-1$$$, если $$$s_i$$$ это символ «-».

Каждая из следующих $$$q$$$ строк содержит два целых положительных числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — числа, описывающие вопросы Спарки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$, а также сумма $$$q$$$ по всем тестовым случаям не превосходит $$$3 \cdot 10^5$$$.

Гарантируется, что сумма ответов (минимальное количество стержней, которое можно удалить) по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выводите ответ в следующем формате:

В первой строке должно находиться одно целое число $$$k$$$ — минимальное количество стержней, которое можно удалить.

Во второй строке должны находиться $$$k$$$ чисел, разделенных пробелом — номера удаляемых стержней.

Если существует несколько правильных вариантов ответа, вы можете вывести любой.

Пример
Входные данные
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
Выходные данные
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$$$, тогда останется следующий набор стержней: ---++-. Нетрудно видеть, что здесь знакопеременная сумма равна нулю.
  • Для третьего запроса можно не удалять стержни вовсе.