В мире последовательностей нет гороскопов. Поэтому когда две последовательности хотят понять, могут ли они счастливо жить вместе, они оценивают свою совместимость как длину их наибольшей общей подпоследовательности.
Подпоследовательность получается из последовательности удалением некоторого (возможно, нулевого) числа элементов. То есть элементы сохраняют свой относительный порядок, но не обязаны изначально идти подряд.
Найдите наибольшую общую подпоследовательность двух одиноких последовательностей и выведите её!
В первой строке дано число n — количество элементов в первой последовательности (1 ≤ n ≤ 1000).
Во второй строке даны n чисел ai (0 ≤ |ai| ≤ 109) — элементы первой последовательности.
Аналогично в третьей строке дано m (1 ≤ m ≤ 1000) — число элементов второй последовательности.
В четвертой строке даны элементы второй последовательности через пробел bi (0 ≤ |bi| ≤ 109).
Сначала выведите длину найденной наибольшей общей подпоследовательности, во второй строке выведите индексы элементов первой последовательности, которые в ней участвуют, в третьей строке — индексы элементов второй последовательности. Нумерация индексов с единицы, индексы должны идти в корректном порядке.
Если возможных НОП несколько, то выведите любую.
|
5 4 9 2 4 6 7 9 4 0 0 2 8 4 |
3 1 3 4 2 5 7 |
|
4 1 1 1 1 2 2 2 |
0 |
|
8 1 2 1 9 1 2 1 9 5 9 9 1 9 9 |
3 3 4 8 3 4 5 |