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

В 144-й аудитории университета ИТМО на двух шкафах в ряд расставлены кубки за победы студентов кафедры КТ на олимпиадах по спортивному программированию.

На первом шкафу в ряд стоят $$$n$$$ кубков, $$$i$$$-й из которых выигран на олимпиаде, которой мы условно присвоим идентификационный номер $$$a_i$$$. Аналогично, $$$i$$$-й из $$$m$$$ кубков на втором шкафу взят на олимпиаде номер $$$b_i$$$. Известно, что на каждом шкафу стоят кубки за разные олимпиады, то есть $$$a_i \neq a_j$$$ и $$$b_i \neq b_j$$$ при $$$i \neq j$$$. При этом не обязательно, что все $$$n + m$$$ кубков различны, бывает такое, что $$$a_i = b_j$$$. Кубки, взятые за одну и ту же олимпиаду, следует считать одинаковыми.

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

Чтобы сохранить эстетику аудитории, было решено выбрать такую последовательность кубков $$$c$$$, что и $$$a$$$, и $$$b$$$ входят в нее в качестве подпоследовательностей. Подпоследовательность — элементы на не обязательно идущих подряд индексах $$$i_1 < i_2 < \ldots < i_k$$$. Например, последовательность $$$[1, 2, 3]$$$ является подпоследовательностью $$$[2, \textcolor{blue}{1}, 5, \textcolor{blue}{2}, 4, 6, \textcolor{blue}{3}]$$$.

Поскольку места на одном шкафу не так много, последовательность $$$c$$$ должна иметь как можно меньшую длину. А для большей гармоничности среди всех подходящих $$$c$$$ минимальной длины следует выбрать ту, которая начинается на как можно меньший первый элемент.

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

В первой строке входных данных даны два числа $$$n$$$ и $$$m$$$ — длины последовательностей $$$a$$$ и $$$b$$$, соответственно ($$$1 \le n, m \le 2 \cdot 10^5$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — номера олимпиад, на которых были взяты кубки на первом шкафу ($$$1 \le a_i \le 10^9$$$). В третьей строке в том же формате перечислены $$$m$$$ целых чисел $$$b_i$$$ — номера олимпиад кубков на втором шкафу ($$$1 \le b_i \le 10^9$$$).

Гарантируется, что все $$$a_i$$$ различны и все $$$b_i$$$ различны.

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

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

В следующей строке выведите элементы самой последовательности $$$c$$$ длины $$$k$$$ через пробел. Если существует несколько подходящих последовательностей длины $$$k$$$, выведите ту из них, которая начинается на меньший элемент. Среди всех таких можно выбрать любую.

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
110$$$n, m \le 10$$$, $$$1 \le a[i], b[i] \le 10$$$полная
215$$$n, m \le 100$$$1первая ошибка
318$$$a_ilt; a_{i+1}$$$ и $$$b_ilt; b_{i+1}$$$ для всех $$$i$$$первая ошибка
411$$$n \le m$$$; $$$a_i \le m$$$, $$$b_ilt; b_{i+1}$$$ для всех $$$i$$$первая ошибка
519$$$n, m \le 2000$$$1, 2первая ошибка
627нет1 — 5первая ошибка

Примеры

Входные данные
1 1
1
2
Выходные данные
2
1 2 
Входные данные
4 4
1 2 3 4
2 1 3 4
Выходные данные
5
1 2 1 3 4