Если увлечься темой кодирования информации, можно поймать себя на придумывании совершенно неожиданных алгоритмов. Сегодня вам предстоит разобраться в кодировании массива стеком.
Изначально вам дан пустой стек и пустой массив. Кодом массива \(a\) назовем последовательность действий вида
-
\(\mathtt{push}(x)\) — положить число \(x\) на вершину стека;
-
\(\mathtt{pop}\) — снять число с вершины стека;
-
\(\mathtt{print}\) — выписать в конец массива все элементы стека по порядку от нижнего к верхнему,
приводящую к тому, что в изначально пустой массив оказываются выписаны все элементы \(a\) по порядку. При выполнении третьей операции стек не очищается.
Например, при выполнении последовательности действий \(\mathtt{push}(1)\), \(\mathtt{push}(2)\), \(\mathtt{print}\), \(\mathtt{print}\), \(\mathtt{pop}\) и \(\mathtt{print}\) в массив оказываются выписаны числа \([1, 2, 1, 2, 1]\), а на стеке остается лежать только число \(1\). То есть такая последовательность является кодом массива \([1, 2, 1, 2, 1]\) длины \(6\).
Вам дан массив \(a\) и \(q\) запросов: какой у отрезка массива \(a\) с \(l_i\)-го по \(r_i\)-й элемент включительно минимальный по количеству действий со стеком код?
Найдите для каждого запроса код соответствующего отрезка массива. Не требуется найти код наименьшей возможной длины, но чем меньше найденный код, тем больше баллов получит ваше решение.
Формат входных данных
В первой строке ввода даны четыре целых числа \(n\) и \(q\) — длина массива \(a\), про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр \(\gamma\), указанный в системе оценивания, которые ваше решение может игнорировать \((1 \le n \le 2000\); \(1 \le q \le 10^4\)).
Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\) (\(1 \le a_i \le 10^9\)).
В \(i\)-й из следующих \(q\) строк даны два целых числа \(l_i\) и \(r_i\) — границы отрезка из \(i\)-го запроса (\(1 \le l_i \le r_i \le n\)).
Формат выходных данных
Для каждого запроса выведите в отдельной строке целое число \(k\) от \(1\) до \(n + 1\) — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел \(k\) целых чисел, описывающих эти действия в порядке их выполнения:
-
для действия \(\mathtt{push}(x)\) выведите число \(x\) от \(1\) до \(10^9\);
-
для действия \(\mathtt{pop}\) выведите число \(-1\);
-
для действия \(\mathtt{print}\) выведите число \(0\).
Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива \(a\), ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше \(n + 1\) действия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
4
0
1
1
2
3
1
2
3
1
2
3
1
9
1
6
4
9
4
6
|
6
1 2 3 0 0 0
5
1 2 3 0 0
5
1 2 3 0 0
4
1 2 3 0
|
|
2
|
12
4
0
1
1
2
3
4
1
2
3
1
2
3
4
5
1
12
2
11
3
10
6
7
|
10
1 2 3 4 0 -1 0 4 5 0
11
2 3 4 1 2 3 1 2 3 4 0
9
3 4 1 2 3 1 2 3 0
3
2 3 0
|