← 返回题目列表

Codeforces · 543/E

E. 听音乐

中文机器翻译题面 查看原题

请注意,内存限制与标准不同。

你真的很喜欢听音乐。在接下来的每一天,您将听到播放列表中的 m 首歌曲,该播放列表由 n 首歌曲组成。让我们用从 1 到 n(含)的数字对播放列表中的歌曲进行编号。第 i 首歌曲的质量为 ai。

在第 i 天,你选择某个整数 v (li ≤ v ≤ ri) 并听编号为 v, v + 1, ..., v + m - 1 的歌曲。在第 i 天,听一首质量低于 qi 的歌曲会使你的不满情绪增加一倍。

确定在接下来的每一天你能得到的最小的不满是多少。

输入

第一行包含两个正整数n、m (1 ≤ m ≤ n ≤ 2·105)。第二行包含 n 个正整数 a1, a2, ..., an (0 ≤ ai < 230) — 播放列表中歌曲的描述。

下一行包含一个数字 s (1 ≤ s ≤ 2·105) — 您考虑的天数。

接下来的 s 行包含三个整数,分别为 li、ri、xi (1 ≤ li ≤ ri ≤ n - m + 1; 0 ≤ xi < 230) — 第 i 天的参数描述。为了计算 qi 值,您需要使用公式: $$q_{i} = x_{i} \oplus ans_{i-1}$$,其中 ansi 是第 i 天问题的答案。假设 ans0 = 0。

输出

准确打印 s 个整数 ans1, ans2, ..., anss,其中 ansi 是您在第 i 天可以获得的最小不满。

示例

输入 #1

5 3
1 2 1 2 3
5
1 1 2
1 3 2
1 3 3
1 3 5
1 3 1

输出 #1

2
0
2
3
1