问题描述

给定一个长度为 $n$ 的序列和一个常数 $w$, 所给序列中的任意一个数 $x$ 满足 $0 \leq x < n$.

对于一个序列 $a_1, a_2, ... , a_n$, 定义区间 $[l, r]$ 为序列 $a_l, a_{l+1}, ... , a_r$.
现在每次给你一个询问 $(l,r,k)$, 表示对所给序列询问区间 $[l,r]$ 中第 $k$ 小的数.

但是需要注意的是, 如果这段区间中的某一个数 $x$ 出现次数超过了 $w$ 次, 则在求第 $k$ 小的数时应将所有的数字 $x$ 视为数字 $n$.

即: 询问时将区间中所有出现次数超过 $w$ 的数字视为数字 $n$.

举例说明:

询问的区间中的数为 $[0,0,0,7,8,8], w = 2, n = 9$, 该区间应视为 $[9,9,9,7,8,8]$;

询问的区间中的数为 $[9,7,8,2,3,3], w = 3, n = 7$, 该区间应视为 $[9,7,8,2,3,3]$;

询问的区间中的数为 $[9,7,5,5,6,6], w = 1, n = 8$, 该区间应视为 $[9,7,8,8,8,8]$;

输入格式

注意, 本题部分测试点 强制在线 .

第一行四个整数 $n, w, q, opt$, 其中 $q$ 表示询问的个数, $opt$ 为强制在线的参数.

第二行 $n$ 个整数 $a_1, a_2, ... , a_n$, 表示序列中的每一个数.

接下来 $q$ 行, 每行三个正整数 $l, r, k$, 表示询问区间 $[l,r]$ 在根据题目要求转化后的第 $k$ 小.

注意这里的 $l,r,k$ 是经过加密的. 记上一次询问的答案为 $lastans$ (初始值为 $0$), 将 $l, r, k$ 分别异或 $opt \times lastans$ 后即为本次询问. 保证询问合法且有解.

输出格式

共 $q$ 行, 每行一个数, 依次表示每个询问的答案.

数据范围

对于 $100\%$ 的数据, 满足 $0 \leq a_i < n \leq 10^5, 0 < q, w \leq 10^5, 0 \leq opt \leq 1$.