题目描述

给出一个长度为 $m$ 的排列 $b$ 和一个长度为 $n$ 的序列 $a$。

如果一个序列 $S$，满足其按位置从左到右依次匹配 $b$ 的一个区间从左到右的位置，那么我们说 $S$ 是一个「优美序列」。

给出 $q$ 次询问。每次询问给出两个整数 $l$ 和 $r$。你需要找到一个 $a$ 的 $[l,r]$ 子区间中的一个最长的满足「优美序列」条件的子序列长度。注意子序列可以不连续。

输入格式

• 第一行输入四个整数 $m,n,q,T$，其中 $n,m,q$ 的含义见「题目描述」，$T$ 表示是否强制在线。
• 第二行输入 $m$ 个整数 $b_1,b_2,\cdots,b_m$。
• 第三行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
• 接下来 $q$ 行每行输入两个整数 $l',r'$。若 $T=1$，则你需要将 $l'$ 和 $r'$ 按位异或 $\mathit{lastans}$ 来得到真正的 $l,r$。其定义为上一次询问操作得到的答案，若之前没有询问操作，则为 $0$。否则若 $T=0$，则 $l=l',r=r'$。

输出格式

• 输出共 $q$ 行。
• 第 $i$ 行输出一个整数，表示第 $i$ 次询问的答案。

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

提示

样例解释

$\mathit{lastans}$ 解密后的询问为：

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

数据范围

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{分值} & \bm{{n,m\le}} &\bm{{q\le}} & \bm{{T=}} & \textbf{特殊性质} & \textbf{Subtask 依赖}\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} $$

• 特殊性质 $\textbf{A}$：保证 $a_i,b_i,l,r$ 在数据范围内均匀随机。

对于 $100\%$ 的数据，$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\}$。