「RdOI R3.5」RMSQ

给出一个长度为 $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}$ 解密后的询问为： ```plain 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\}$。