CF543E.Listening to Music

Please note that the memory limit differs from the standard.

You really love to listen to music. During the each of next s days you will listen to exactly m songs from the playlist that consists of exactly n songs. Let's number the songs from the playlist with numbers from 1 to n, inclusive. The quality of song number i is a__i.

On the i-th day you choose some integer v (l__i ≤ v ≤ r__i) and listen to songs number v, v + 1, ..., v + m - 1. On the i-th day listening to one song with quality less than q__i increases your displeasure by exactly one.

Determine what minimum displeasure you can get on each of the s next days.

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

你非常喜欢听音乐。在接下来的 $s$ 天中，每天你都将恰好从一个包含 $n$ 首歌曲的播放列表中听 $m$ 首歌。我们将播放列表中的歌曲编号为 $1$ 到 $n$（含端点）。第 $i$ 首歌曲的质量为 $a_i$。

在第 $i$ 天，你选择某个整数 $v$（满足 $l_i \le v \le r_i$），并依次收听编号为 $v,\, v+1,\, \dots,\, v+m-1$ 的 $m$ 首歌曲。在第 $i$ 天，每收听一首质量低于 $q_i$ 的歌曲，你的不愉快值就会恰好增加 $1$。

请确定你在接下来的 $s$ 天中，每天所能达到的最小不愉快值。

The first line contains two positive integers n, m (1 ≤ m ≤ n ≤ 2·105). The second line contains n positive integers _a_1, _a_2, ..., a__n (0 ≤ a__i < 230) — the description of songs from the playlist.

The next line contains a single number s (1 ≤ s ≤ 2·105) — the number of days that you consider.

The next s lines contain three integers each l__i, r__i, x__i (1 ≤ l__i ≤ r__i ≤ n - m + 1; 0 ≤ x__i < 230) — the description of the parameters for the i-th day. In order to calculate value q__i, you need to use formula: , where ans__i is the answer to the problem for day i. Assume that _ans_0 = 0.

第一行包含两个正整数 $n$、$m$（$1 ≤ m ≤ n ≤ 2·10^5$）。第二行包含 $n$ 个正整数 $a_1, a_2, ..., a_n$（$0 ≤ a_i < 2^{30}$）——表示播放列表中各首歌曲的描述。

接下来一行包含一个整数 $s$（$1 ≤ s ≤ 2·10^5$）——表示你所考虑的天数。

接下来的 $s$ 行每行包含三个整数 $l_i, r_i, x_i$（$1 ≤ l_i ≤ r_i ≤ n - m + 1$；$0 ≤ x_i < 2^{30}$）——表示第 $i$ 天的参数。为计算值 $q_i$，需使用公式：，其中 $ans_i$ 是第 $i$ 天对应问题的答案。规定 $ans_0 = 0$。

Print exactly s integers _ans_1, _ans_2, ..., ans__s, where ans__i is the minimum displeasure that you can get on day i.

精确输出 s 个整数：_ans_₁, _ans_₂, ..., ans__s，其中 ans__i 表示第 i 天所能达到的最小不愉快度。