A team of researchers is studying the similarities between sequences of hieroglyphs. They represent each hieroglyph with a non-negative integer. To perform their study, they use the following concepts about sequences.

For a fixed sequence $A$, a sequence $S$ is called a subsequence of $A$ if and only if $S$ can be obtained by removing some elements (possibly none) from $A$.

The table below shows some examples of subsequences of a sequence $A=[3,2,1,2]$.

Subsequence	How it can be obtained from $A$
[3, 2, 1, 2]	No elements are removed.
[2, 1, 2]	[3, 2, 1, 2]
[3, 2, 2]	[3, 2, 1, 2]
[3, 2]	[3, 2, 1, 2] or [3, 2, 1, 2]
[3]	[3, 2, 1, 2]
[ ]	[3, 2, 1, 2]

On the other hand, $[3,3]$ or $[1,3]$ are not subsequences of $A$.

Consider two sequences of hieroglyphs, $A$ and $B$. A sequence $S$ is called a common subsequence of $A$ and $B$ if and only if $S$ is a subsequence of both $A$ and $B$. Moreover, we say that a sequence $U$ is a universal common subsequence of $A$ and $B$ if and only if the following two conditions are met:

• $U$ is a common subsequence of $A$ and $B$.
• Every common subsequence of $A$ and $B$ is also a subsequence of $U$.

It can be shown that any two sequences $A$ and $B$ have at most one universal common subsequence.

The researchers have found two sequences of hieroglyphs $A$ and $B$. Sequence $A$ consists of $N$ hieroglyphs and sequence $B$ consists of $M$ hieroglyphs. Help the researchers compute a universal common subsequence of sequences $A$ and $B$, or determine that such a sequence does not exist.

Implementation details

You should implement the following procedure.

std::vector<int> ucs(std::vector<int> A, std::vector<int> B)

• $A$: array of length $N$ describing the first sequence.
• $B$: array of length $M$ describing the second sequence.
• If there exists a universal common subsequence of $A$ and $B$, the procedure should return an array containing this sequence. Otherwise, the procedure should return $[-1]$ (an array of length $1$, whose only element is $-1$).
• This procedure is called exactly once for each test case.

Constraints

• $1\le N\le 100000$
• $1\le M\le 100000$
• $0\le A[i]\le 200000$ for each $i$ such that $0\le i<N$
• $0\le B[j]\le 200000$ for each $j$ such that $0\le j<M$

Subtasks

Subtask	Score	Additional Constraints
1	$3$	$N=M$; each of $A$ and $B$ consists of $N$ distinct integers between $0$ and $N-1$ (inclusive)
2	$15$	For any integer $k$, (the number of elements of $A$ equal to $k$) plus (the number of elements of $B$ equal to $k$) is at most $3$.
3	$10$	$A[i]\le 1$ for each $i$ such that $0\le i<N$; $B[j]\le 1$ for each $j$ such that $0\le j<M$
4	$16$	There exists a universal common subsequence of $A$ and $B$.
5	$14$	$N\le 3000$; $M\le 3000$
6	$42$	No additional constraints.

Examples

Example 1

Consider the following call.

ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])

Here, the common subsequences of $A$ and $B$ are the following: $[]$, $[0]$, $[1]$, $[2]$, $[0,0]$, $[0,1]$, $[0,2]$, $[1,0]$, $[1,2]$, $[0,0,2]$, $[0,1,0]$, $[0,1,2]$, $[1,0,2]$ and $[0,1,0,2]$.

Since $[0,1,0,2]$ is a common subsequence of $A$ and $B$, and all common subsequences of $A$ and $B$ are subsequences of $[0,1,0,2]$, the procedure should return $[0,1,0,2]$.

Example 2

Consider the following call.

ucs([0, 0, 2], [1, 1])

Here, the only common subsequence of $A$ and $B$ is the empty sequence $[]$. It follows that the procedure should return an empty array $[]$.

Example 3

Consider the following call.

ucs([0, 1, 0], [1, 0, 1])

Here, the common subsequences of $A$ and $B$ are $[],[0],[1],[0,1]$ and $[1,0]$. It can be shown that a universal common subsequence does not exist. Therefore, the procedure should return $[-1]$.

Sample Grader

Input format:

N  M
A[0]  A[1]  ...  A[N-1]
B[0]  B[1]  ...  B[M-1]

Output format:

T
R[0]  R[1]  ...  R[T-1]

Here, $R$ is the array returned by ucs and $T$ is its length.

Attachment Package

The sample grader along with sample test cases are available here.