407863: GYM102906 F Не подпоследовательность

F. Не подпоследовательностьограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Последовательность $$$X = [x_1, x_2, \ldots, x_t]$$$ является подпоследовательностью последовательности $$$Y = [y_1, y_2, \ldots, y_s]$$$, если можно удалить некоторые (возможно ни одного) элементы $$$Y$$$, чтобы получить $$$X$$$. Иначе говоря, существует последовательность индексов $$$1 \le i_1 < i_2 < \ldots < i_t \le s$$$, что $$$x_j = y_{i_j}$$$ для всех $$$j$$$ от $$$1$$$ до $$$s$$$. Например, последовательность $$$[1, 2, 3, 2]$$$ является подпоследовательностью последовательности $$$[\mathbf{1}, 1, \mathbf{2}, 2, 1, \mathbf{3}, \mathbf{2}, 1]$$$, а последовательность $$$[1, 2, 3, 1, 2]$$$ — нет.

Рассмотрим две последовательности $$$A = [a_1, a_2, \ldots, a_m]$$$ и $$$B = [b_1, b_2, \ldots, b_n]$$$, состоящие из целых чисел от $$$1$$$ до $$$k$$$.

Требуется найти минимальную по длине последовательность $$$C = [c_1, c_2, \ldots, c_p]$$$, которая не являлась бы подпоследовательностью ни $$$A$$$ ни $$$B$$$. Элементы последовательности $$$C$$$ также должны являться целыми числами от $$$1$$$ до $$$k$$$.

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

Первая строка ввода содержит число $$$k$$$ — максимальное значение элемента последовательности ($$$1 \le k \le 5\,000$$$).

Вторая строка содержит число $$$m$$$ — длину последовательности $$$A$$$ ($$$1 \le m \le 5\,000$$$). Третья строка содержит $$$m$$$ целых чисел от $$$1$$$ до $$$k$$$ — последовательность $$$A$$$.

Четвертая строка содержит число $$$n$$$ — длину последовательности $$$B$$$ ($$$1 \le n \le 5\,000$$$). Пятая строка содержит $$$n$$$ целых чисел от $$$1$$$ до $$$k$$$ — последовательность $$$B$$$.

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

На первой строке выведите $$$p$$$ — длину искомой последовательности. На второй строке выведите последовательность $$$C$$$. Если оптимальных ответов несколько, выведите любой из них.

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

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

Подзадача	Баллы	Доп. ограничения	Необх. подзадачи
1	11	$$$k = 1$$$
2	10	$$$k = 2$$$; $$$1 \le m, n \le 10$$$
3	10	$$$k = 2$$$; $$$1 \le m, n \le 200$$$	2
4	10	$$$k = 2$$$; $$$1 \le m, n \le 5000$$$	2, 3
5	15	$$$1 \le m, n \le 10$$$	2
6	15	$$$1 \le m, n \le 200$$$	2, 3, 5
7	29	$$$1 \le m, n \le 5000$$$	1–6

ПримерВходные данные

2
5
1 2 1 2 1
5
2 1 2 1 2

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

4
1 1 1 1