Problem Description

You are given a permutation $b$ of length $m$ and a sequence $a$ of length $n$.

If a sequence $S$ can be matched, from left to right by positions, to the positions from left to right of some interval of $b$, then we call $S$ a "beautiful sequence".

You are given $q$ queries. In each query, two integers $l$ and $r$ are given. You need to find, within the subarray $[l,r]$ of $a$, the maximum length of a subsequence that satisfies the "beautiful sequence" condition. Note that a subsequence does not need to be contiguous.

Input Format

• The first line contains four integers $m,n,q,T$, where the meanings of $n,m,q$ are as described in the statement, and $T$ indicates whether online processing is forced.
• The second line contains $m$ integers $b_1,b_2,\cdots,b_m$.
• The third line contains $n$ integers $a_1,a_2,\cdots,a_n$.
• The next $q$ lines each contain two integers $l',r'$. If $T=1$, you need to compute the real $l,r$ by bitwise XOR of $l'$ and $r'$ with $\mathit{lastans}$. Here, $\mathit{lastans}$ is defined as the answer to the previous query; if there was no previous query, it is $0$. Otherwise, if $T=0$, then $l=l',r=r'$.

Output Format

• Output a total of $q$ lines.
• On the $i$-th line, output one integer, the answer to the $i$-th query.

4 6 6 1
1 2 3 4
1 2 3 2 3 4
1 3
2 7
1 7
0 7
0 4
2 5

3
3
2
2
3
4

Hint

Sample Explanation

The queries after decrypting with $\mathit{lastans}$ are:

1 3
1 4
2 4
2 5
2 6
1 6

Constraints

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{Score} & \bm{{n,m\le}} &\bm{{q\le}} & \bm{{T=}} & \textbf{Special Property} & \textbf{Subtask Dependencies}\cr\hline 1 & 10 & 100 & 10^4 & 1 & \textbf{A} & -\cr\hline 2 & 15 & 10^5 & 10^5 & 1 & \textbf{A} & 1\cr\hline 3 & 30 & 3\times 10^5 & 10^6 & 0 & - & -\cr\hline 4 & 45 & 3\times 10^5 & 10^6 & 1 & - & 2,3\cr\hline \end{array}$$

• Special property $\textbf{A}$: it is guaranteed that $a_i,b_i,l,r$ are uniformly random within the constraints.

For $100\%$ of the testdata, $1\le l\le r\le n\le 3\times 10^5$, $1\le a_i\le m\le 3\times 10^5$, $1\le q \le 1\times 10^6$, $T \in \{0,1\}$.

Translated by ChatGPT 5