请注意,内存限制与标准不同。
你真的很喜欢听音乐。在接下来的每一天,您将听到播放列表中的 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