Longest Common Subsequence in Two Sequences

You are given a list of sequences of integers. Your task is to find the longest subsequence (not necessarily contiguous) that appears as a subsequence in at least two different sequences.

A subsequence is obtained by deleting zero or more elements from the sequence without changing the order of the remaining elements. In case there are multiple longest subsequences, you should output the lexicographically smallest one. Here, lexicographical order is determined by comparing corresponding elements from left to right.

If no common subsequence exists (i.e. no non-empty subsequence appears in at least two sequences), output -1.

Note: It is guaranteed that the sequences are small enough so that a brute force approach will work.

Example:

• For sequences [1,2,3,4,5,6], [5,6,7,8,9] and [1,2,8,9,10], the possible longest common subsequences of length 2 are [5,6] and [8,9]. Since [5,6] is lexicographically smaller than [8,9] (because 5 < 8), the answer is 5 6.
• For sequences [1,3,7], [2,3,8] and [3,9,10], the answer is 3.
• If there is no common subsequence at all, output -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n1 a1 a2 ... an1
n2 b1 b2 ... bn2
...
nT x1 x2 ... xnT

Here, T is the number of sequences. For each sequence, the first number is the length of that sequence, followed by the integers in the sequence.

outputFormat

Print the longest common subsequence that appears in at least two sequences on a single line, with the numbers separated by a single space. If no such subsequence exists, print -1.

## sample

3
6 1 2 3 4 5 6
5 5 6 7 8 9
5 1 2 8 9 10

5 6