Longest Common Subsequence

Let X = (x₁, x₂, …, x_n) be a sequence. A sequence S = (s₁, s₂, …, s_k) is a subsequence of X if there exist the integers 0 < i₁ < i₂ < … < i_k ≤ n such that s_j = x_ij 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 = (x₁, x₂, …, x_m), Y = (y₁, y₂, …, y_n), and Z = (z₁, z₂, …, z_k), 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