Это сложная версия задачи. Различия между версиями заключаются в том, что в сложной версии требуется выводить номера удаляемых стержней. Вы можете делать взломы, только если обе версии задачи сданы.
Стич любит экспериментировать с различными механизмами вместе со своим другом Спарки. Сегодня они построили очередную машину.
Главным элементом этой машины являются \(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\) включительно, какое минимальное количество стержней можно было бы удалить из машины так, чтобы знакопеременная сумма зарядов на оставшихся была равна нулю? Также Спарки хочет знать номера этих стержней. Возможно, друзья что-то напутали, и знакопеременная сумма уже равна нулю. В таком случае, можно не удалять стержни вовсе.
Если количество стержней равно нулю, будем считать, что знакопеременная сумма зарядов равна нулю, то есть всегда можно удалить все стержни.
Помогите друзьям и ответьте на все вопросы Спарки!
Выходные данные
Для каждого набора входных данных выводите ответ в следующем формате:
В первой строке должно находиться одно целое число \(k\) — минимальное количество стержней, которое можно удалить.
Во второй строке должны находиться \(k\) чисел, разделенных пробелом — номера удаляемых стержней.
Если существует несколько правильных вариантов ответа, вы можете вывести любой.
Примечание
В первом наборе входных данных для первого запроса можно удалить стержни под номерами \(5\) и \(8\), тогда останется следующий набор стержней: +--+--++-++-. Нетрудно видеть, что здесь знакопеременная сумм равна нулю.
В втором наборе входных данных:
- Для первого запроса можно удалить стержни под номерами \(1\) и \(11\), тогда останется следующий набор стержней: --++---++---. Нетрудно видеть, что здесь знакопеременная сумма равна нулю.
- Для второго запроса можно удалить стержень под номером \(9\), тогда останется следующий набор стержней: ---++-. Нетрудно видеть, что здесь знакопеременная сумма равна нулю.
- Для третьего запроса можно не удалять стержни вовсе.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|