问题描述

​ 现有 $n$ 个正整数 $a_1,\ a_2,\ ...,\ a_n$ 以及一个参数 $k$。

​ 定义一个大小为 $x$ 的有序集合 $S = \{p_1,\ p_2,\ ...,\ p_x\}$ 在 $t$ 意义下是能入眼的，当且仅当对所有 $1 \leqslant i < x$，$t \leqslant p_i < p_{i+1}$。

​ 定义一个大小为 $x$ 的有序集合 $S = \{p_1,\ p_2,\ ...,\ p_x\}$ 在 $t$ 意义下为优美集，当且仅当它在 $t$ 意义下能入眼且不存在 $1 \leqslant i \leqslant x$ 使得 $|a_{p_i} - a_{p_1}| >k$。

​ 多次查询满足 $\{x,\ x+1, ...,\ y\} \subseteq S$ 的最大在 $t$ 意义下的优美集 $S$ 的大小。部分测试点强制在线。

输入格式

​ 第一行一个正整数表示测试点编号。

​ 第二行四个正整数 $n,\ k,\ Qnum,\ o$。 $Qnum$ 代表询问个数，$o$ 为 0 或 1，表示是否强制在线。

​ 接下来一行 $n$ 个正整数表示 $a_1,\ a_2,\ ...,\ a_n$。

​ 接下来 $Qnum$ 行，每行三个整数 $t,\ x,\ y$。如果 $o = 1$，你需要把 $t$，$x$ 和 $y$ 异或上上一次询问的答案，异或的操作符为 ^ 或 $\operatorname{xor}$。

​ 保证解密后 $x \leqslant y$。

输出格式

​ 对于每个询问输出一行答案。不存在满足条件的集合输出 $0$。

-1
5 3 2 0
1 4 2 4 8
1 2 3
2 4 5

4
0

样例 2

​ 见目录下 tot2.in/ans。该样例满足数据点 2-3 且 o = 1 的性质。

样例 3

​ 见目录下 tot3.in/ans。该样例满足数据点 9 的性质。

样例解释 1

​ 对于第一组询问，如下集合 $S$ 满足：

2 3
2 3 4
1 2 3 4
1 2 3

​ 其中第三个最大，大小为 $4$。

​ 对于第二组询问，没有集合满足。

数据规模与约定

​ 请注意常数因子对得分的影响。

对于所有数据，保证 $1 \leqslant a_i,\ k \leqslant 10^9$，$1 \leqslant x,\ y \leqslant n$，$a_i$ 在 $[1, 10^9]$ 中使用以时间为种子的自带随机函数生成。

权值为 $i$ 的特殊性质 1：$y - x \leqslant i$。

特殊性质 2：$x \leqslant 50$。

特殊性质 3：$t = 1$。

以上特殊性质均指解密后。

大样例

大样例下载