Problem Description

Given three digit strings $A, B, C$, find a longest common subsequence of $A$ and $B$ such that $C$ is a substring of this subsequence.

Input Format

The first line contains an integer $n$, the length of $A$.

The second line contains $n$ integers, representing the digit string $A$.

The third line contains an integer $m$, the length of $B$.

The fourth line contains $m$ integers, representing the digit string $B$.

The fifth line contains an integer $k$, the length of $C$.

The sixth line contains $k$ integers, representing the digit string $C$.

Output Format

Output one line with one integer. If there is no solution, output $-1$; otherwise, output the length of the longest common subsequence that satisfies the condition.

7
1 2 2 3 1 1 2
6
1 2 1 3 1 2
2
3 2

4

Hint

For $100\%$ of the testdata, $1 \leq n, m \leq 3 \times 10^3$, $0 \leq k \leq 3 \times 10^3$.

Translated by ChatGPT 5