В 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$$$, выведите ту из них, которая начинается на меньший элемент. Среди всех таких можно выбрать любую.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке | ||
1 | 10 | $$$n, m \le 10$$$, $$$1 \le a[i], b[i] \le 10$$$ | полная | |||
2 | 15 | $$$n, m \le 100$$$ | 1 | первая ошибка | ||
3 | 18 | $$$a_i | lt; a_{i+1}$$$ и $$$b_i | lt; b_{i+1}$$$ для всех $$$i$$$ | первая ошибка | |
4 | 11 | $$$n \le m$$$; $$$a_i \le m$$$, $$$b_i | lt; b_{i+1}$$$ для всех $$$i$$$ | первая ошибка | ||
5 | 19 | $$$n, m \le 2000$$$ | 1, 2 | первая ошибка | ||
6 | 27 | нет | 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