Most Complete Common Subsequence

A research team is studying the similarity between sequences of hieroglyphs. Each hieroglyph is represented by a non‐negative integer. Given a sequence \(A\), a sequence \(S\) is called a subsequence of \(A\) if and only if \(S\) can be obtained by deleting some (possibly zero) elements from \(A\). For example, if \(A=[3,2,1,2]\), some subsequences of \(A\) are:

On the other hand, sequences such as [3, 3] or [1, 3] are not subsequences of \(A\).

Given two hieroglyph sequences \(A\) and \(B\) (with \(A\) having \(N\) elements and \(B\) having \(M\) elements), a sequence \(S\) is called a common subsequence if it is a subsequence of both \(A\) and \(B\). Furthermore, a sequence \(U\) is called the most complete common subsequence of \(A\) and \(B\) if:

• \(U\) is a common subsequence of \(A\) and \(B\); and
• Every common subsequence of \(A\) and \(B\) is a subsequence of \(U\).

It can be proved that any two sequences \(A\) and \(B\) have at most one most complete common subsequence. Note that the empty sequence is considered a subsequence. In particular, if the only common subsequence is empty, then the most complete common subsequence is the empty sequence.

Your task is to find the most complete common subsequence of \(A\) and \(B\) if it exists, or determine that it does not exist. In this problem, it turns out that the most complete common subsequence exists if and only if the longest common subsequence (LCS) is unique. Therefore, you only need to compute the LCS between \(A\) and \(B\) and also check its uniqueness. If a unique LCS exists, output it; otherwise, output -1.

Input Format:
The first line contains two integers \(N\) and \(M\).
The second line contains \(N\) non‐negative integers representing sequence \(A\).
The third line contains \(M\) non‐negative integers representing sequence \(B\).

Output Format:
If the most complete common subsequence exists, print the subsequence (the numbers separated by a space). If it does not exist, print -1. If the most complete common subsequence is the empty sequence, print an empty line.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\), the lengths of sequences \(A\) and \(B\) respectively. The next line contains \(N\) non‐negative integers representing sequence \(A\), and the following line contains \(M\) non‐negative integers representing sequence \(B\).

outputFormat

If a unique most complete common subsequence exists, output its elements separated by a space. If it does not exist, output -1. (If the most complete common subsequence is empty, output an empty line.)

sample

4 3
3 2 1 2
3 1 2

3 1 2