Стековое кодирование
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Если увлечься темой кодирования информации, можно поймать себя на придумывании совершенно неожиданных алгоритмов. Сегодня вам предстоит разобраться в кодировании массива стеком.

Изначально вам дан пустой стек и пустой массив. Кодом массива $$$a$$$ назовем последовательность действий вида

приводящую к тому, что в изначально пустой массив оказываются выписаны все элементы $$$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$$$ целых чисел, описывающих эти действия в порядке их выполнения:

Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива $$$a$$$, ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше $$$n + 1$$$ действия.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом. То есть, если вы получаете вердикт WA на каком-либо тесте в группе, вы получаете $$$0$$$ баллов за всю группу. Если все тесты группы пройдены с положительным вердиктом, вы получаете сумму баллов за все тесты в группе.

Для каждой подзадачи даны общие для тестов этой подзадачи ограничения и параметр $$$\gamma$$$, показывающий, насколько близкое к ответу жюри решение будет засчитываться на ненулевой балл.

Если ваше решение для $$$i$$$-го запроса в конкретном тесте строит код из $$$p_i$$$ действий, а решение жюри строит код из $$$j_i$$$ действий, то за этот тест ваше решение получает $$$$$$\max\left(0, \mathtt{score} - \max\left(0, \max\limits_{i=1}^q \left\lfloor\frac{p_i - j_i}{\gamma}\right\rfloor\right)\right) \text{ баллов,}$$$$$$ где $$$\mathtt{score}$$$ — максимальный балл за этот тест. Иными словами, за каждые $$$\gamma$$$ действий свыше решения жюри в каком-либо из запросов вы теряете один балл за тест.

Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.

ПодзадачаБаллыОграничения$$$\gamma$$$ Необходимые подзадачи Информация о проверке
0$$$2 \times 0$$$примеры из условия$$$100$$$полная
1$$$4 \times 1$$$$$$n \le 10$$$$$$10$$$0первая ошибка
2$$$4 \times 1$$$$$$n \le 10$$$$$$1$$$0, 1первая ошибка
3$$$4 \times 1$$$$$$n \le 200$$$, $$$q = 1$$$$$$1$$$первая ошибка
4$$$5 \times 2$$$$$$q = 1$$$$$$1$$$3первая ошибка
5$$$5 \times 2$$$$$$n \le 200$$$$$$1$$$0 – 3первая ошибка
6$$$4 \times 1$$$$$$a_i = 1$$$ для всех $$$i$$$$$$100$$$первая ошибка
7$$$5 \times 2$$$$$$a_i = 1$$$ для всех $$$i$$$$$$1$$$6первая ошибка
8$$$5 \times 3$$$ $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ $$$50$$$6, 7первая ошибка
9$$$5 \times 2$$$ $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ $$$2$$$6 – 8первая ошибка
10$$$9 \times 2$$$$$$q \le 4000$$$$$$50$$$0 – 9первая ошибка
11$$$11 \times 1$$$$$$q \le 4000$$$$$$2$$$0 – 10первая ошибка

Примеры

Входные данные
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 
Входные данные
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