A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.  Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences. 

Given two sequences of integers, $A=[a[1],a[2],...,a[n]]$ and $B=[b[1],b[2],...,b[m]]$, find the longest common subsequence and print it as a line of space-separated integers. If there are multiple common subsequences with the same maximum length, print any one of them.

In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.    

Recommended References  

This Youtube video tutorial explains the problem and its solution quite well.  

Function Description  

Complete the longestCommonSubsequence function in the editor below.  It should return an integer array of a longest common subsequence.  

longestCommonSubsequence has the following parameter(s):  

a: an array of integers  
b: an array of integers

Input Format

The first line contains two space separated integers $n$ and $m$, the sizes of sequences $\mbox{A}$ and $\mbox{B}$. 

The next line contains $n$ space-separated integers $A[i]$. 

The next line contains $m$ space-separated integers $B[j]$.

Constraints  

$1\leq n\leq100$ 

$1\leq m\leq100$ 

$0\leq a[i]<1000,\ \text{where}\ i\in[1,n]$ 

$0\leq b[j]<1000,\ \text{where}\ j\in[1,m]$  

Constraints

$1\le n,m\le100$ 

$0\leq a[i],b[j]<1000$  

Output Format

Print the longest common subsequence as a series of space-separated integers on one line. In case of multiple valid answers, print any one of them.

Sample Input
5 6
1 2 3 4 1
3 4 1 2 1 3

Sample Output
1 2 3

Explanation

There is no common subsequence with length larger than 3. And "1 2 3",  "1 2 1", "3 4 1" are all correct answers.  

Tested by Khongor

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(xLength, yLength) = list(map(int, input().split(' ')))
xValues = list(input().split(' '))
yValues = list(input().split(' '))
table = []
for x in range(xLength):
	col = []
	for y in range(yLength):
		col.append(0)
	table.append(col)
for y in range(yLength):
	for x in range(xLength):
		if xValues[x] == yValues[y]:
			if x == 0 or y == 0:
				table[x][y] = 1
			else:
				table[x][y] = table[x - 1][y - 1] + 1
		elif x == 0 and y == 0:
			table[x][y] = 0
		elif x == 0:
			table[x][y] = table[x][y - 1]
		elif y == 0:
			table[x][y] = table[x - 1][y]
		else:
			table[x][y] = max(table[x][y - 1], table[x - 1][y])
foundLCS = False
x = xLength - 1
y = yLength - 1
LCS = []
while not foundLCS:
	t = table[x][y]
	if x == 0 and y == 0:
		LCS.append(xValues[x])
		foundLCS = True
	elif x == 0:
		if table[x][y - 1] == t:
			y -= 1
		else:
			LCS.append(xValues[x])
			foundLCS = True
	elif y == 0:
		if table[x - 1][y] == t:
			x -= 1
		else:
			LCS.append(xValues[x])
			foundLCS = True
	elif table[x - 1][y] == t:
		x -= 1
	elif table[x][y - 1] == t:
		y -= 1
	else:
		LCS.append(xValues[x])
		t = table[x - 1][y - 1]
		x -= 1
		y -= 1
		if t == 0:
			foundLCS = True
LCS.reverse()
print(' '.join(LCS))


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
prev = [0] * len(A)
tracking = []
for b_char in B:
	row = []
	t = []
	for (i, a_char) in enumerate(A):
		if a_char == b_char:
			row.append(prev[i - 1] + 1 if i > 0 else 1)
			t.append((i, row[-1]))
		else:
			row.append(max(prev[i], row[i - 1] if i > 0 else 0))
	if t:
		tracking.append(t)
	prev = row
lcs = []
untracked_lcs_length = None
while tracking:
	t = tracking.pop()
	while t:
		(i, l) = t.pop()
		if untracked_lcs_length is None or untracked_lcs_length - 1 == l:
			untracked_lcs_length = l
			lcs.append(i)
			break
lcs.reverse()
print(*[A[i] for i in lcs])


def backtrack(c, x, y, i=None, j=None):
	i = i if i is not None else len(x) - 1
	j = j if j is not None else len(y) - 1
	if i < 0 or j < 0:
		return []
	if x[i] == y[j]:
		return backtrack(c, x, y, i - 1, j - 1) + [x[i]]
	if c[i][j - 1] > c[i - 1][j]:
		return backtrack(c, x, y, i, j - 1)
	return backtrack(c, x, y, i - 1, j)

def lcs(x, y):
	c = [[0 for j in range(len(y) + 1)] for i in range(len(x) + 1)]
	for i in range(len(x)):
		for j in range(len(y)):
			if x[i] == y[j]:
				c[i][j] = c[i - 1][j - 1] + 1
			else:
				c[i][j] = max(c[i][j - 1], c[i - 1][j])
	return backtrack(c, x, y)
	return c[len(x) - 1][len(y) - 1]
(n, m) = map(int, input().split())
(A, B) = (list(map(int, input().split())) for i in range(2))
result = lcs(A, B)
print(' '.join(map(str, result)))


dynamic_memory = dict()

def dynamic(a1, a2, i1=0, i2=0):
	if (i1, i2) in dynamic_memory:
		return dynamic_memory[i1, i2]
	elif i1 < len(a1) and i2 < len(a2):
		if a1[i1] == a2[i2]:
			res = [a1[i1]] + dynamic(a1, a2, i1 + 1, i2 + 1)
			dynamic_memory[i1, i2] = res
		else:
			res1 = dynamic(a1, a2, i1, i2 + 1)
			res2 = dynamic(a1, a2, i1 + 1, i2)
			if len(res2) > len(res1):
				res = res2
			else:
				res = res1
			dynamic_memory[i1, i2] = res
		return res
	else:
		return []
(n, m) = [int(i) for i in input().split()]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = dynamic(a, b)
print(*res)


nm = [int(x) for x in input().split(' ')]
n = nm[0]
m = nm[1]
c = []
vector1 = [int(x) for x in input().split(' ')]
vector2 = [int(x) for x in input().split(' ')]
c.append([])
for i in range(0, m + 1):
	c[0].append(0)
for i in range(0, n):
	c.append([0])
for i in range(0, n):
	for j in range(0, m):
		if vector1[i] == vector2[j]:
			c[i + 1].append(c[i][j] + 1)
		else:
			c[i + 1].append(max(c[i][j + 1], c[i + 1][j]))
answer = []
i = n
j = m
while c[i][j] != 0:
	if c[i][j] == c[i - 1][j]:
		i = i - 1
	elif c[i][j] == c[i][j - 1]:
		j = j - 1
	else:
		answer = [str(vector1[i - 1])] + answer
		i = i - 1
		j = j - 1
print(' '.join(answer))


def lcs(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			lengths[i + 1][j + 1] = lengths[i][j] + 1 if x == y else max(lengths[i + 1][j], lengths[i][j + 1])
	result = []
	(x, y) = (len(a), len(b))
	while x != 0 and y != 0:
		if lengths[x][y] == lengths[x - 1][y]:
			x -= 1
		elif lengths[x][y] == lengths[x][y - 1]:
			y -= 1
		else:
			result = [a[x - 1]] + result
			x -= 1
			y -= 1
	print(*result)
(n, m) = map(int, input().split())
lcs([int(_) for _ in input().split()], [int(_) for _ in input().split()])


import sys

def lcs(n, m):
	for i in range(n + 1):
		for j in range(m + 1):
			if i == 0 or j == 0:
				c[i][j] = 0
			elif a[i - 1] == b[j - 1]:
				c[i][j] = c[i - 1][j - 1] + 1
			else:
				c[i][j] = max(c[i][j - 1], c[i - 1][j])

def trace():
	length = c[n][m]
	(i, j) = (n, m)
	final = []
	while length > 0:
		if a[i - 1] == b[j - 1]:
			final.insert(0, a[i - 1])
			i = i - 1
			j = j - 1
			length = length - 1
		elif c[i - 1][j] == length:
			i = i - 1
		elif c[i][j - 1] == length:
			j = j - 1
	return final
lines = [[int(val) for val in line.split()] for line in sys.stdin]
([n, m], a, b) = lines
c = []
for i in range(n + 1):
	inside = []
	for j in range(m + 1):
		inside.append(0)
	c.append(inside)
lcs(n, m)
print(' '.join(list(map(str, trace()))))


import sys, itertools
(n, m) = map(int, input().split())
seq1 = list(map(int, input().split()))
seq2 = list(map(int, input().split()))
LCS = [[0] * (m + 1) for _ in range(n + 1)]
backref = [[(None, None)] * (m + 1) for _ in range(n + 1)]
for (i, ai) in enumerate(seq1, start=1):
	for (j, bj) in enumerate(seq2, start=1):
		if ai == bj:
			LCS[i][j] = LCS[i - 1][j - 1] + 1
			backref[i][j] = (i, j)
		elif LCS[i][j - 1] > LCS[i - 1][j]:
			LCS[i][j] = LCS[i][j - 1]
			backref[i][j] = backref[i][j - 1]
		else:
			LCS[i][j] = LCS[i - 1][j]
			backref[i][j] = backref[i - 1][j]
res = []
if seq1[n - 1] == seq2[m - 1]:
	(i, j) = (n, m)
else:
	(i, j) = backref[n][m]
while i != None:
	res.append(seq1[i - 1])
	(i, j) = backref[i - 1][j - 1]
print(' '.join(map(str, reversed(res))))


len_of_strings = input()
str1 = input().split(' ')
str2 = input().split(' ')

def LCS_value(X, Y):
	m = len(X)
	n = len(Y)
	c = {}
	b = {}
	for i in range(0, len(X) + 1):
		c[i, 0] = 0
	for j in range(len(Y) + 1):
		c[0, j] = 0
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if X[i - 1] == Y[j - 1]:
				c[i, j] = c[i - 1, j - 1] + 1
				b[i, j] = 'Across'
			elif c[i - 1, j] >= c[i, j - 1]:
				c[i, j] = c[i - 1, j]
				b[i, j] = 'Up'
			else:
				c[i, j] = c[i, j - 1]
				b[i, j] = ' '
	return print_LCS(b, X, m, n)

def print_LCS(b, X, i, j):
	s = ''
	while i != 0 and j != 0:
		if b[i, j] == 'Across':
			s = X[i - 1] + ' ' + s
			i = i - 1
			j = j - 1
		elif b[i, j] == 'Up':
			i = i - 1
		else:
			j = j - 1
	return s[:-1]
print(LCS_value(str1, str2))


d = {}

def lcs(s1, s2):
	if (s1, s2) in d.keys():
		return d[s1, s2]
	if len(s1) * len(s2) == 0:
		d[s1, s2] = ''
		return d[s1, s2]
	if s1[-1] == s2[-1]:
		d[s1, s2] = s1[-1] + '/' + lcs(s1[:len(s1) - 1], s2[:len(s2) - 1])
		return d[s1, s2]
	else:
		temp1 = lcs(s1, s2[:len(s2) - 1])
		temp2 = lcs(s1[:len(s1) - 1], s2)
		d[s1, s2] = temp1 if len(temp1) > len(temp2) else temp2
		return d[s1, s2]
(n, m) = [int(i) for i in input().split()]
st1 = [i for i in input().split()]
st2 = [i for i in input().split()]
(st1, st2) = (tuple(st1), tuple(st2))
temp = lcs(st1, st2).split('/')
print(' '.join(temp[::-1])[1:])


(n, m) = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
b = [int(v) for v in input().split()]
dp = dict()
for i in range(n):
	for j in range(m):
		wk = []
		if a[i] == b[j]:
			wk.append(list([a[i]]))
			if i - 1 >= 0 and j - 1 >= 0:
				wk.append(dp[i - 1, j - 1] + [a[i]])
		else:
			if i - 1 >= 0 and j - 1 >= 0:
				wk.append(dp[i - 1, j - 1])
			if i - 1 >= 0:
				wk.append(dp[i - 1, j])
			if j - 1 >= 0:
				wk.append(dp[i, j - 1])
		if len(wk) != 0:
			maxlen = max((len(v) for v in wk))
			for v in wk:
				if len(v) == maxlen:
					dp[i, j] = v
					break
		else:
			dp[i, j] = []
print(*dp[n - 1, m - 1])


(n, m) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
s_lengths = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
sequences = [[[] for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if A[i - 1] == B[j - 1]:
			s_lengths[i][j] = 1 + s_lengths[i - 1][j - 1]
			sequences[i][j] = list(sequences[i - 1][j - 1])
			sequences[i][j].append(A[i - 1])
		elif s_lengths[i - 1][j] >= s_lengths[i][j - 1]:
			s_lengths[i][j] = s_lengths[i - 1][j]
			sequences[i][j] = sequences[i - 1][j]
		else:
			s_lengths[i][j] = s_lengths[i][j - 1]
			sequences[i][j] = sequences[i][j - 1]
print(' '.join(map(str, sequences[-1][-1])))


(n, m) = [int(x) for x in input().split()]
a = input().split()
b = input().split()
S = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if a[i - 1] == b[j - 1]:
			S[i][j] = max(S[i][j - 1], S[i - 1][j], 1 + S[i - 1][j - 1])
		else:
			S[i][j] = max(S[i][j - 1], S[i - 1][j])
substring = []
(i, j) = (n, m)
while i > 0 and j > 0:
	if S[i][j] == S[i - 1][j]:
		i -= 1
	elif S[i][j] == S[i][j - 1]:
		j -= 1
	else:
		substring.append(a[i - 1])
		i -= 1
		j -= 1
print(' '.join(reversed(substring)))


def iterative():
	import sys
	read = sys.stdin.readline
	(m, n) = map(int, input().split())
	A = read().split()
	B = read().split()
	dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
	ans = []
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if A[i - 1] == B[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	i = m
	j = n
	while len(ans) != dp[m][n]:
		if A[i - 1] == B[j - 1]:
			ans.append(A[i - 1])
			i -= 1
			j -= 1
		elif dp[i - 1][j] >= dp[i][j]:
			i -= 1
		else:
			j -= 1
	ans.reverse()
	print(' '.join(ans))
iterative()


def iterative():
	import sys
	read = sys.stdin.readline
	(m, n) = map(int, input().split())
	A = read().split()
	B = read().split()
	dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
	ans = []
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if A[i - 1] == B[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	i = m
	j = n
	while len(ans) != dp[m][n]:
		if A[i - 1] == B[j - 1]:
			ans.append(A[i - 1])
			i -= 1
			j -= 1
		elif dp[i - 1][j] >= dp[i][j]:
			i -= 1
		else:
			j -= 1
	ans.reverse()
	print(' '.join(ans))
iterative()


import sys
case_num = len(sys.stdin.readline().split())
seq1 = [int(i) for i in sys.stdin.readline().split()]
seq2 = [int(i) for i in sys.stdin.readline().split()]
dp = [[[] for i in range(len(seq2) + 1)] for j in range(2)]
for i in range(len(seq1)):
	for j in range(len(seq2)):
		if seq1[i] == seq2[j]:
			dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + [seq1[i]]
		else:
			dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j], key=lambda t: len(t))
result = ''
for i in dp[len(seq1) % 2][-1]:
	result += str(i) + ' '
print(result[:-1])


(N, M) = map(int, input().rstrip().split(' '))
A = list(map(int, input().rstrip().split(' ')))
B = list(map(int, input().rstrip().split(' ')))
dp = [[0] * (N + 1) for _ in range(M + 1)]
for m in range(1, M + 1):
	for n in range(1, N + 1):
		s = 1 if A[n - 1] == B[m - 1] else 0
		dp[m][n] = max(dp[m - 1][n], dp[m][n - 1], dp[m - 1][n - 1] + s)

def trace_back(m, n, res):
	if n == 0 or m == 0:
		return
	if dp[m][n] - 1 == dp[m - 1][n - 1] and A[n - 1] == B[m - 1]:
		res.append(A[n - 1])
		trace_back(m - 1, n - 1, res)
	elif dp[m][n] == dp[m][n - 1]:
		trace_back(m, n - 1, res)
	else:
		trace_back(m - 1, n, res)
res = []
trace_back(M, N, res)
print(' '.join(reversed(list(map(str, res)))))


from itertools import product
(n, m) = list(map(int, input().split()))
a = input().split()
b = input().split()
table = {}
for (i, j) in product(range(len(a)), range(len(b))):
	if a[i] == b[j]:
		table[i, j] = table.get((i - 1, j - 1), 0) + 1
	else:
		table[i, j] = max(table.get((i - 1, j), 0), table.get((i, j - 1), 0))
sequence = []
while i >= 0 and j >= 0:
	val = table[i, j]
	while table.get((i - 1, j), 0) == val:
		i -= 1
	while table.get((i, j - 1), 0) == val:
		j -= 1
	sequence.append(a[i])
	i -= 1
	j -= 1
print(' '.join(map(str, reversed(sequence))))


def lcs(x, y):
	(n, m) = (len(x), len(y))
	dp = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if x[i - 1] == y[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
	return dp

def lcs_solution(table, x, y):
	(n, m) = (len(x), len(y))
	s = []
	while table[n][m] > 0:
		if x[n - 1] == y[m - 1]:
			s.append(x[n - 1])
			n -= 1
			m -= 1
		elif table[n - 1][m] >= table[n][m - 1]:
			n -= 1
		else:
			m -= 1
	return s[::-1]
_ = input()
a = list(map(int, input().split()))
b = list(map(int, input().split()))
table = lcs(a, b)
print(' '.join(map(str, lcs_solution(table, a, b))))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
memo = [[(0, None)] * m for _ in range(n)]
for i in range(n):
	for j in range(m):
		if a[i] == b[j]:
			prev = memo[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else (0, None)
			if memo[i][j][0] < prev[0] + 1:
				memo[i][j] = (prev[0] + 1, a[i], prev)
		prev = memo[i - 1][j] if i - 1 >= 0 else (0, None)
		if memo[i][j][0] < prev[0]:
			memo[i][j] = prev
		prev = memo[i][j - 1] if j - 1 >= 0 else (0, None)
		if memo[i][j][0] < prev[0]:
			memo[i][j] = prev
res = []
curr = memo[n - 1][m - 1]
while curr[1] is not None:
	res.append(curr[1])
	curr = curr[2]
print(str(list(reversed(res))).strip('[]').replace(',', ''))


from collections import defaultdict
readinput = lambda x: [int(y) for y in x.split()]
(N, M) = readinput(input())
string_n = readinput(input())
string_m = readinput(input())
LCS = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(N):
	for j in range(M):
		if string_n[i] == string_m[j]:
			LCS[i + 1][j + 1] = LCS[i][j] + 1
		else:
			LCS[i + 1][j + 1] = max(LCS[i][j + 1], LCS[i + 1][j])
(i, j) = (N, M)
output = []
while i > 0 and j > 0:
	if string_n[i - 1] == string_m[j - 1]:
		output.append(string_n[i - 1])
		i -= 1
		j -= 1
	elif LCS[i - 1][j] >= LCS[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(' '.join([str(x) for x in output[::-1]]))


def longest_common_subsequence_table(N, M, A, B):
	C = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if A[i - 1] == B[j - 1]:
				C[i][j] = C[i - 1][j - 1] + 1
			else:
				C[i][j] = max(C[i][j - 1], C[i - 1][j])
	return C

def longest_common_subsequence(N, M, A, B):
	C = longest_common_subsequence_table(N, M, A, B)
	S = []
	while N != 0 and M != 0:
		if C[N][M] == C[N - 1][M]:
			N -= 1
		elif C[N][M] == C[N][M - 1]:
			M -= 1
		elif A[N - 1] == B[M - 1]:
			S.insert(0, A[N - 1])
			N -= 1
			M -= 1
	return ' '.join((str(s) for s in S))

def main():
	(N, M) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	print(longest_common_subsequence(N, M, A, B))
main()


(n, m) = map(int, input().split())
nArray = list(map(int, input().split()))
mArray = list(map(int, input().split()))
output = []
DP = [0] * (m + 1)
DP[0] = [0] * (n + 1)
for i in range(1, m + 1):
	DP[i] = [0] * (n + 1)
	for j in range(1, n + 1):
		if mArray[i - 1] == nArray[j - 1]:
			DP[i][j] = DP[i - 1][j - 1] + 1
		else:
			DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])
i = m
j = n
while i > 0 and j > 0:
	if DP[i][j] == DP[i - 1][j - 1] + 1 and mArray[i - 1] == nArray[j - 1]:
		output.append(nArray[j - 1])
		i = i - 1
		j = j - 1
	elif DP[i][j] == DP[i][j - 1]:
		j = j - 1
	else:
		i = i - 1
output.reverse()
print(' '.join(map(str, output)))


def equals(x, y):
	if x == y:
		return [x]
	else:
		return []

def start():
	(n, m) = input().split()
	A = [int(s) for s in input().split()]
	B = [int(t) for t in input().split()]

	def LCS(i, j):
		dp = [[[] for x in range(j + 1)] for y in range(i + 1)]
		for x in range(1, i + 1):
			for y in range(1, j + 1):
				one = dp[x - 1][y]
				two = dp[x][y - 1]
				three = dp[x - 1][y - 1] + equals(A[x - 1], B[y - 1])
				dp[x][y] = max(one, two, three, key=lambda x: len(x))
		print(' '.join((str(s) for s in dp[i][j])))
	i = len(A)
	j = len(B)
	LCS(i, j)
start()


def findLCS(seqA, seqB):
	lcs = [[0 for x in range(len(seqA) + 1)] for y in range(len(seqB) + 1)]
	for i in range(1, len(seqB) + 1):
		for j in range(1, len(seqA) + 1):
			if seqA[j - 1] == seqB[i - 1]:
				lcs[i][j] = lcs[i - 1][j - 1] + 1
			else:
				lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j])
	return lcs

def returnLCSseq(seqA, seqB, lcs):
	i = len(seqB)
	j = len(seqA)
	result = [0] * lcs[i][j]
	while lcs[i][j] != 0:
		if seqA[j - 1] == seqB[i - 1]:
			result[lcs[i][j] - 1] = seqA[j - 1]
			i -= 1
			j -= 1
		elif lcs[i][j - 1] == lcs[i][j]:
			j -= 1
		else:
			i -= 1
	return result
(n, m) = [int(x) for x in input().split()]
seqA = [int(x) for x in input().split()]
seqB = [int(x) for x in input().split()]
lcs = findLCS(seqA, seqB)
result = returnLCSseq(seqA, seqB, lcs)
print(' '.join([str(x) for x in result]))


def LCS(a, b):
	lengths = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
	for (i, x) in enumerate(a):
		for (j, y) in enumerate(b):
			if x == y:
				lengths[i + 1][j + 1] = lengths[i][j] + 1
			else:
				lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])
	result = []
	(x, y) = (len(a), len(b))
	while x != 0 and y != 0:
		if lengths[x][y] == lengths[x - 1][y]:
			x -= 1
		elif lengths[x][y] == lengths[x][y - 1]:
			y -= 1
		else:
			assert a[x - 1] == b[y - 1]
			result.append(a[x - 1])
			x -= 1
			y -= 1
	return result[::-1]

def actions():
	while True:
		yield input()
go = actions()
(n, m) = [int(i) for i in next(go).split()]
A = [int(i) for i in next(go).split()]
B = [int(i) for i in next(go).split()]
print(' '.join(map(str, LCS(A, B))))


(A, B) = map(int, input().strip().split())
seq1 = list(map(int, input().strip().split()))
seq2 = list(map(int, input().strip().split()))
C = []
for m in range(len(seq1) + 1):
	C.append([])
	for n in range(len(seq2) + 1):
		C[m].append(0)
for i in range(1, len(seq1) + 1):
	for j in range(1, len(seq2) + 1):
		if seq1[i - 1] == seq2[j - 1]:
			C[i][j] = C[i - 1][j - 1] + 1
		else:
			C[i][j] = max(C[i][j - 1], C[i - 1][j])

def backtrack_(i, j):
	if i == 0 or j == 0:
		return []
	elif seq1[i - 1] == seq2[j - 1]:
		return backtrack_(i - 1, j - 1) + [seq1[i - 1]]
	elif C[i][j - 1] > C[i - 1][j]:
		return backtrack_(i, j - 1)
	else:
		return backtrack_(i - 1, j)
print(' '.join(map(str, backtrack_(len(seq1), len(seq2)))))


def LCS_dp(X, Y, table, I, J):
	for j in range(1, J + 1):
		for i in range(1, I + 1):
			if X[i - 1] == Y[j - 1]:
				table[j][i] = 1 + table[j - 1][i - 1]
			else:
				table[j][i] = max(table[j - 1][i], table[j][i - 1])
	return table

def trace_route(X, Y, table, I, J):
	path = []
	while I > 0 and J > 0:
		while table[J][I] == table[J][I - 1] and I >= 0:
			I -= 1
		if X[I - 1] == Y[J - 1]:
			path.append(X[I - 1])
		else:
			while table[J][I] == table[J - 1][I] and J >= 0:
				J -= 1
			if X[I - 1] == Y[J - 1]:
				path.append(Y[J - 1])
		I -= 1
		J -= 1
	path.reverse()
	print(' '.join((str(x) for x in path)))
[I, J] = [int(x) for x in input().strip().split()]
A = [str(x) for x in input().strip().split()]
B = [str(x) for x in input().strip().split()]
table = [[0 for X in range(len(A) + 1)] for Y in range(len(B) + 1)]
table = LCS_dp(A, B, table, len(A), len(B))
trace_route(A, B, table, len(A), len(B))


def longestSharedSubset(a, b):
	ix_a = {}
	for i in range(len(a)):
		if a[i] in ix_a:
			ix_a[a[i]].append(i)
		else:
			ix_a[a[i]] = [i]
	ix_b_a = []
	for i in range(len(b)):
		if b[i] in ix_a:
			ix_b_a.append(ix_a[b[i]])
	max = 0
	dp = []
	prev = []
	dp.append([])
	prev.append([])
	for i in range(len(ix_b_a[0])):
		dp[0].append(1)
		prev[0].append([-1, -1])
	for i in range(1, len(ix_b_a)):
		dp.append([])
		prev.append([])
		for j in range(len(ix_b_a[i])):
			dp[i].append(1)
			prev[i].append([-1, -1])
			for k in range(i):
				for l in range(len(ix_b_a[k])):
					if ix_b_a[i][j] > ix_b_a[k][l]:
						if dp[i][j] < dp[k][l] + 1:
							dp[i][j] = dp[k][l] + 1
							prev[i][j] = [k, l]
							max = [i, j]
	ret = []
	ret.append(a[ix_b_a[max[0]][max[1]]])
	max = prev[max[0]][max[1]]
	while max[0] >= 0:
		ret.insert(0, a[ix_b_a[max[0]][max[1]]])
		max = prev[max[0]][max[1]]
	return ret
input()
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
ret = longestSharedSubset(a, b)
ret_str = '' + str(ret[0])
for i in range(1, len(ret)):
	ret_str += ' ' + str(ret[i])
print(ret_str)


def lcs_len(s1, s2):
	s1_len = len(s1)
	s2_len = len(s2)
	tab = [[None] * (s2_len + 1) for i in range(s1_len + 1)]
	for i in range(s1_len + 1):
		for j in range(s2_len + 1):
			if i == 0 or j == 0:
				tab[i][j] = 0
			elif s1[i - 1] == s2[j - 1]:
				tab[i][j] = 1 + tab[i - 1][j - 1]
			else:
				tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
	index = tab[s1_len][s2_len]
	lcs = [''] * (index + 1)
	lcs[index] = '\x00'
	i = s1_len
	j = s2_len
	while i > 0 and j > 0:
		if s1[i - 1] == s2[j - 1]:
			lcs[index - 1] = s1[i - 1]
			i -= 1
			j -= 1
			index -= 1
		elif tab[i][j - 1] > tab[i - 1][j]:
			j -= 1
		else:
			i -= 1
	return ' '.join(lcs[:len(lcs) - 1])
(n, m) = list(map(int, input().split()))
s1 = input().split()
s2 = input().split()
print(lcs_len(s1, s2))


from functools import lru_cache
import sys
sys.setrecursionlimit(3000)
input()
a = input().split()
b = input().split()

@lru_cache(None)
def get(i, j):
	if i == len(a) or j == len(b):
		return []
	if a[i] == b[j]:
		return get(i + 1, j + 1) + [a[i]]
	q = get(i + 1, j)
	w = get(i, j + 1)
	if len(q) > len(w):
		return q
	return w
print(' '.join(get(0, 0)[::-1]))


d = ((-1, -1), (-1, 0), (0, -1))
(N, M) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
dp = [[0 for i in range(M)] for i in range(N)]
con = [[None for i in range(M)] for i in range(N)]
for i in range(M):
	if a[0] == b[i]:
		dp[0][i] = 1
	elif i > 0 and dp[0][i - 1] == 1:
		dp[0][i] = 1
		con[0][i] = d[2]
for i in range(N):
	if a[i] == b[0]:
		dp[i][0] = 1
	elif i > 0 and dp[i - 1][0] == 1:
		dp[i][0] = 1
		con[i][0] = d[1]
for i in range(1, N):
	for j in range(1, M):
		if a[i] == b[j] and dp[i][j] < dp[i - 1][j - 1] + 1:
			dp[i][j] = dp[i - 1][j - 1] + 1
			con[i][j] = d[0]
		for _d in d[1:]:
			if dp[i][j] < dp[i + _d[0]][j + _d[1]]:
				dp[i][j] = dp[i + _d[0]][j + _d[1]]
				con[i][j] = _d
(i, j) = (N - 1, M - 1)
lcss = []
if a[i] == b[j]:
	lcss.append(a[i])
while con[i][j] != None:
	_d = con[i][j]
	i += _d[0]
	j += _d[1]
	if a[i] == b[j]:
		lcss.append(a[i])
print(' '.join(map(str, reversed(lcss))))


def LCS(A, B, N, M):
	DPT = [[0] * (M + 1) for _ in range(N + 1)]
	for a in range(1, N + 1):
		for b in range(1, M + 1):
			if A[a - 1] == B[b - 1]:
				DPT[a][b] = DPT[a - 1][b - 1] + 1
			else:
				DPT[a][b] = max(DPT[a][b - 1], DPT[a - 1][b])
	(a, b) = (N, M)
	toReturn = []
	while a > 0 and b > 0:
		if A[a - 1] == B[b - 1]:
			toReturn.append(A[a - 1])
			(a, b) = (a - 1, b - 1)
		elif DPT[a][b - 1] > DPT[a - 1][b]:
			(a, b) = (a, b - 1)
		else:
			(a, b) = (a - 1, b)
	return ' '.join(toReturn[::-1])
(N, M) = tuple(map(int, input().split()))
A = input().split()
B = input().split()
print(LCS(A, B, N, M))


def main():
	arr = input().split()
	n = int(arr[0])
	m = int(arr[1])
	a = input().split()
	b = input().split()
	calcmat(a, b)

def calcmat(a, b):
	mat = [['' for y in range(len(a) + 1)] for x in range(len(b) + 1)]
	if len(a) == 0 or len(b) == 0:
		print('EMPTY')
	else:
		for i in range(1, len(a) + 1):
			for j in range(1, len(b) + 1):
				if b[j - 1] == a[i - 1]:
					if len(mat[j - 1][i - 1]) != 0:
						mat[j][i] = mat[j - 1][i - 1] + ' ' + a[i - 1]
					else:
						mat[j][i] += a[i - 1]
				else:
					if len(mat[j][i - 1]) == len(mat[j - 1][i]):
						lon = mat[j][i - 1]
					elif len(mat[j][i - 1]) > len(mat[j - 1][i]):
						lon = mat[j][i - 1]
					else:
						lon = mat[j - 1][i]
					mat[j][i] += lon
		print(mat[len(b)][len(a)])
main()


from sys import stderr
(An, Bm) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
mem = {}

def lcs(a, n, b, m):
	if a[n - 1] == b[m - 1]:
		(x, s) = lcs_mem(a, n - 1, b, m - 1)
		return (x + 1, s + [a[n - 1]])
	else:
		p1 = lcs_mem(a, n - 1, b, m)
		p2 = lcs_mem(a, n, b, m - 1)
		return p1 if p1[0] >= p2[0] else p2

def lcs_mem(a, n, b, m):
	if not n or not m:
		return (0, [])
	key = (n, m)
	pair = mem.get(key)
	if not pair:
		pair = lcs(a, n, b, m)
		mem[key] = pair
	return pair
(x, s) = lcs_mem(A, An, B, Bm)
print(' '.join(map(str, s)))
for k in sorted(mem.keys()):
	print('k=%s, v=%s' % (k, mem[k]), file=stderr)


def f(i, j):
	if i == 0 or j == 0:
		return
	if x[i - 1] == y[j - 1]:
		table[i][j] = [table[i - 1][j - 1][0] + 1, -1, -1]
	else:
		table[i][j] = [max(table[i][j - 1][0], table[i - 1][j][0]), -1 * (table[i - 1][j][0] >= table[i][j - 1][0]), -1 * (table[i - 1][j][0] < table[i][j - 1][0])]
(n, m) = [int(a) for a in input().strip().split()]
x = [int(a) for a in input().strip().split()]
y = [int(a) for a in input().strip().split()]
table = [[[0, 0, 0] for i in range(m + 1)] for j in range(n + 1)]
for i in range(n + 1):
	for j in range(m + 1):
		f(i, j)
output = []
ni = n
mi = m
while ni > 0 and mi > 0:
	if table[ni][mi][1] == table[ni][mi][2]:
		output.append(x[ni - 1])
		ni = ni - 1
		mi = mi - 1
	elif table[ni][mi][1] == -1:
		ni = ni - 1
	elif table[ni][mi][2] == -1:
		mi = mi - 1
output.reverse()
print(*output)


(n, m) = [int(x) for x in input().split()]
A = input().split()
B = input().split()
arr = [[0 for j in range(m + 1)] for i in range(n + 1)]
s = [[[] for j in range(m + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if A[i - 1] == B[j - 1]:
			arr[i][j] = arr[i - 1][j - 1] + 1
			s[i][j] = s[i - 1][j - 1] + [A[i - 1]]
		elif arr[i - 1][j] >= arr[i][j - 1]:
			arr[i][j] = arr[i - 1][j]
			s[i][j] = s[i - 1][j]
		else:
			arr[i][j] = arr[i][j - 1]
			s[i][j] = s[i][j - 1]
print(' '.join(s[n][m]))


(n, m) = list(map(int, input().split(' ')))
seq_n = list(map(int, input().split(' ')))
seq_m = list(map(int, input().split(' ')))
mn = [[0] * (n + 1) for i in range(m + 1)]
for i in range(1, m + 1):
	for j in range(1, n + 1):
		if seq_m[i - 1] == seq_n[j - 1]:
			mn[i][j] = mn[i - 1][j - 1] + 1
		else:
			mn[i][j] = max(mn[i - 1][j], mn[i][j - 1])
result = []
i = n
j = m
while i > 0 and j > 0:
	if seq_n[i - 1] == seq_m[j - 1]:
		result.append(seq_n[i - 1])
		i -= 1
		j -= 1
	elif mn[j - 1][i] > mn[j][i - 1]:
		j -= 1
	else:
		i -= 1
print(' '.join(map(str, result[::-1])))


(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
prev = [[] for i in range(N + 1)]
curr = [[] for i in range(N + 1)]
for j in range(M):
	best = []
	for i in range(N):
		if A[i] == B[j]:
			best = prev[i] + [A[i]]
		elif len(prev[i + 1]) > len(best):
			best = prev[i + 1]
		curr[i + 1] = best
	(prev, curr) = (curr, prev)
print(' '.join(map(str, best)))


def lcs(a, b):
	mem = [[(0, [])] * len(b) for _ in range(len(a))]
	mx = 0
	if a[0] == b[0]:
		mem[0][0] = (1, [a[0]])
	for ia in range(1, len(a)):
		if a[ia] == b[0]:
			mem[ia][0] = (1, [a[ia]])
		else:
			mem[ia][0] = mem[ia - 1][0]
	for ib in range(1, len(b)):
		if b[ib] == a[0]:
			mem[0][ib] = (1, [a[0]])
		else:
			mem[0][ib] = mem[0][ib - 1]
	for ia in range(1, len(a)):
		for ib in range(1, len(b)):
			if a[ia] == b[ib]:
				mem[ia][ib] = (1 + mem[ia - 1][ib - 1][0], mem[ia - 1][ib - 1][1] + [a[ia]])
			elif mem[ia - 1][ib][0] >= mem[ia][ib - 1][0]:
				mem[ia][ib] = mem[ia - 1][ib]
			else:
				mem[ia][ib] = mem[ia][ib - 1]
	return mem[-1][-1]
input()
a = input().split(' ')
b = input().split(' ')
print(' '.join(lcs(a, b)[1]))


def fillMatrix(row, col):
	L = [[0] * (col + 1) for _ in range(row + 1)]
	for row_index in range(1, row + 1):
		for col_index in range(1, col + 1):
			if string1[row_index - 1] == string2[col_index - 1]:
				L[row_index][col_index] = L[row_index - 1][col_index - 1] + 1
			else:
				L[row_index][col_index] = max(L[row_index - 1][col_index], L[row_index][col_index - 1])
	return L

def findMatrix(string1, matrix, row, col):
	end_list = []
	maxLen = matrix[row][col]
	while maxLen > 0:
		while matrix[row - 1][col] == maxLen:
			row -= 1
		while matrix[row][col] == maxLen:
			col -= 1
		end_list.append(string1[row - 1])
		maxLen -= 1
	return end_list[::-1]
temp = list(map(int, input().split(' ')))
string1 = list(map(int, input().split(' ')))
string2 = list(map(int, input().split(' ')))
row = temp[0]
col = temp[1]
matrix = fillMatrix(row, col)
end_list = findMatrix(string1, matrix, row, col)
print(' '.join((str(elm) for elm in end_list)))


def key(a, b):
	return '{}|{}'.format(len(a), len(b))

def longest_subsequence(a, b, cache):
	cache_value = cache.get(key(a, b))
	if cache_value is not None:
		return cache_value
	if len(a) == 0 or len(b) == 0:
		result = []
	elif a[0] == b[0]:
		result = [a[0]]
		result += longest_subsequence(a[1:], b[1:], cache)
	else:
		delete_a_result = longest_subsequence(a[1:], b, cache)
		delete_b_result = longest_subsequence(a, b[1:], cache)
		if len(delete_a_result) > len(delete_b_result):
			result = delete_a_result
		else:
			result = delete_b_result
	cache[key(a, b)] = result
	return result
(n, m) = input().strip().split(' ')
a = input().strip().split(' ')
b = input().strip().split(' ')
print(' '.join(longest_subsequence(a, b, {})))


cache = {}

def LCSS(A, B):
	len_A = len(A)
	len_B = len(B)
	if len_A < 1 or len_B < 1:
		return []
	if A[-1] == B[-1]:
		key = (len_A - 1, len_B - 1)
		if key not in cache:
			cache[key] = LCSS(A[:len_A - 1], B[:len_B - 1])
		return cache[key] + [A[-1]]
	else:
		left_key = (len_A - 1, len_B)
		if left_key not in cache:
			cache[left_key] = LCSS(A[:len_A - 1], B[:len_B])
		right_key = (len_A, len_B - 1)
		if right_key not in cache:
			cache[right_key] = LCSS(A[:len_A], B[:len_B - 1])
		if len(cache[right_key]) > len(cache[left_key]):
			return cache[right_key]
		else:
			return cache[left_key]
(n, m) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
print(*LCSS(A, B))


def c(i, j, a, b, m):
	if i < 0 or j < 0:
		return 0
	if m[i][j] != None:
		return m[i][j]
	if a[i] == b[j]:
		r = c(i - 1, j - 1, a, b, m) + 1
		m[i][j] = r
		return r
	else:
		r = max(c(i - 1, j, a, b, m), c(i, j - 1, a, b, m))
		m[i][j] = r
		return r

def backtrack(m, a, b, i, j):
	if i < 0 or j < 0:
		return ''
	if a[i] == b[j]:
		return backtrack(m, a, b, i - 1, j - 1) + str(a[i]) + ' '
	if c(i, j - 1, a, b, m) > c(i - 1, j, a, b, m):
		return backtrack(m, a, b, i, j - 1)
	else:
		return backtrack(m, a, b, i - 1, j)
(n, m) = input().split()
(n, m) = (int(n), int(m))
matrix = [[None] * m for i in range(0, n)]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
res = c(n - 1, m - 1, a, b, matrix)
res = backtrack(matrix, a, b, n - 1, m - 1)
print(res.strip())


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
c = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if x[i - 1] == y[j - 1]:
			prev = c[i - 1][j - 1]
			c[i][j] = prev + 1
		else:
			c[i][j] = max(c[i - 1][j], c[i][j - 1])
result = []
i = n
j = m
while i != 0 and j != 0:
	if x[i - 1] == y[j - 1]:
		result.insert(0, x[i - 1])
		i -= 1
		j -= 1
	elif c[i][j] == c[i - 1][j]:
		i -= 1
	else:
		j -= 1
print(' '.join(map(str, result)))