6. НОП с восстановлением ответа

Не решаласьСредняя

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Напомним:

Последовательность $x$ называется подпоследовательностью последовательности $y$, если $x$ получается из $𝑦$ удалением нескольких (возможно, нуля или всех) элементов.

Наибольшая общая подпоследовательность - последовательность наибольшей длины, которая является подпоследовательностью обеих последовательностей.

Формат ввода

В первой строке входных данных содержится число N – длина первой последовательности (1 $\le$ N $\le$ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 $\le$ M $\le$ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Формат вывода

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

Примечание

В примере 2 существует сразу три наибольшие общие подпоследовательности.

1) 1

2) 2

3) 3

Любая из них будет правильным ответом.

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
3
1 2 3
3
2 3 1
Вывод
2 3 

Пример 2

Ввод
3
1 2 3
3
3 2 1
Вывод
1 

Теги

Нужно войти, чтобы отправить решение.Войти