问题描述

给定一个长度为 \(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\).