P9572 "NnOI R2-T4" Colorful Days♪

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$. 2. 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.

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 two integers $c_1 \cdot \operatorname{LCS}(S^k,T)$ and $c_2 \cdot k$.

**[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| Chuanjiang Mowang | |check| Sudohry | |solution| Chuanjiang Mowang | Translated by ChatGPT 5