Longest Common Subsequence
Let X = (x1, x2, …, xn) be a sequence. A sequence S = (s1, s2, …, sk) is a subsequence of X if there exist the integers 0 < i1 < i2 < … < ik ≤ n such that sj = xij for j = 1, 2, …, k. For example: 2, 5, 7, 3 is a subsequence of 2, 9, 5, 7, 8, 1, 3, 4.
Given three sequences of integers: X = (x1, x2, …, xm), Y = (y1, y2, …, yn), and Z = (z1, z2, …, zk), find the longest common subsequence. For example, for the sequences X = (2, 9, 5, 7, 8), Y = (9, 3, 5, 8), Z = (1, 9, 4, 5, 8), the longest common subsequence is (9, 5, 8).
The first line of the input contains the number of test cases. For each test case, there are four lines: The first line of them contains m, n, and k, the numbers of integers in each sequence, separated by a space (1 ≤ m, n, k ≤ 100). Each of the next three lines contains the elements (integer numbers) of a sequence, separated by a space. The sequence elements are integers from the interval [–32768, 32767].
For each test case, print in a line the elements of the longest common subsequence, separated by a space. If there is no solution, print the text “
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|