Problem Description

The following definitions are given:

1. Define $AB$ as the array obtained by concatenating array $A$ followed by array $B$.
2. Define $A^{0}=\{\}$ (i.e., the empty array). For $i=1,2,3,\cdots$, define $A^{i}=A^{i-1}A$.
3. Define $\operatorname{LCS}(A,B)$ as the length of the Longest Common Subsequence of arrays $A$ and $B$.

Now you are given an array $S$ of length $n$ and an array $T$ of length $m$. All numbers in the arrays are positive integers.

You need to find the smallest non-negative integer $k$ such that $\operatorname{LCS}(S^k,T)$ is maximized.

The problem setter is very kind: if you cannot minimize $k$, you can still get partial points.

Input Format

The first line contains four integers $n, m, c_1, c_2$. The last two integers are output parameters, either $0$ or $1$.

The second line contains $n$ positive integers, representing array $S$.

The third line contains $m$ positive integers, representing array $T$.

Output Format

Output two integers $c_1 \cdot \operatorname{LCS}(S^k,T)$ and $c_2 \cdot k$.

3 4 1 1
23 34 53
53 25 23 34

3 2

9 10 1 1
15 12 26 21 26 21 23 12 23
26 11 21 15 16 15 12 23 17 12

7 3

Hint

[Sample 1 Explanation]

When $k = 2$, $S^k = \text{\{23 34 \textcolor{red}{53 23 34} 53\}}$, where the red part is a longest common subsequence of $S^k$ and $T$.

[Constraints]

Note: This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le n, m, S_i, T_i \le 10^6$, and $c_1, c_2 \in \{0,1\}$.

$$\def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c} \textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& c_1=c_2=0 & 2 \r \textsf2& n \le 10^3，m \le 10^2 & 8 \r \textsf3& n \le 10^4，m \le 10^3 & 15 \r \textsf4& c_2=0 & 15 \r \textsf5& n,m \le 10^5，S_i,T_i \le 26 & 20 \r \textsf6& 无特殊限制 & 40 \r \end{array}$$

The newly added hack test points after the contest will be included in subtask 7.

Problem Source

Item	Person
idea	Chuanjiang Mowang
data
check	Sudohry
solution	Chuanjiang Mowang

Translated by ChatGPT 5