# Programming contests

## ECN programozó csapatverseny, 2017. május 13.

May 13, 2017 10:10 AM – May 13, 2017 3:10 PM

# Longest Common Subsequence

Let X = (x1x2, …, xn) be a sequence. A sequence S = (s1s2, …, 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 = (x1x2, …, xm), Y = (y1y2, …, yn), and Z = (z1z2, …, 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).

## Input Specification

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].

## Output Specification

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 “`No solution`”.

## Sample Input

1. `2`
2. `5 4 5`
3. `2 9 5 7 8`
4. `9 3 5 8`
5. `1 9 4 5 8`
6. `4 5 3`
7. `1 2 3 4`
8. `4 3 1 2 0`
9. `7 8 9`
download as text file

## Output for Sample Input

1. `9 5 8`
2. `No solution`
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019