Hieroglyphs

A team of researchers is studying the similarities between sequences of hieroglyphs. Each hieroglyph is represented by a non-negative integer.

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

For example, $\[3, 3]$ and $\[1, 3]$ are not subsequences of $A = \[3, 2, 1, 2]$.

For two sequences $A$ and $B$, a sequence $S$ is a common subsequence of $A$ and $B$ if $S$ is a subsequence of both. A sequence $U$ is a universal common subsequence of $A$ and $B$ if both of the following hold:

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

Any two sequences $A$ and $B$ have at most one universal common subsequence.

The researchers have two sequences $A$ and $B$. Sequence $A$ has $N$ hieroglyphs and sequence $B$ has $M$ hieroglyphs. Compute a universal common subsequence of $A$ and $B$, or determine that none exists.

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $0 \le A[i] \le 200\,000$ for each $i$ such that $0 \le i < N$
• $0 \le B[j] \le 200\,000$ for each $j$ such that $0 \le j < M$