| Codeforces Round 302 (Div. 1) |
|---|
| Закончено |
Обратите внимание на нестандартное ограничение по памяти.
Вы очень любите слушать музыку. В течение следующих s дней вы будете слушать ровно по m песен из плейлиста, который состоит ровно из n песен. Пронумеруем песни из плейлиста числами от 1 до n включительно. Качество песни с номером i равно ai.
В i-й день вы выбираете некоторое целое v (li ≤ v ≤ ri) и слушаете песни с номерами v, v + 1, ..., v + m - 1. Кроме этого, в i-й день прослушивание одной песни с качеством меньше qi увеличивает ваше недовольство ровно на одну единицу.
Определите, какого минимального недовольства возможно достичь в каждый из s следующих дней.
В первой строке записано два целых положительных числа 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 необходимо воспользоваться формулой: 
, где ansi — ответ на задачу для дня i. Будем считать, что ans0 = 0.
Выведите ровно s целых чисел ans1, ans2, ..., anss, где ansi — минимальное недовольство, которого можно достичь в день с номером i.
5 3
1 2 1 2 3
5
1 1 2
1 3 2
1 3 3
1 3 5
1 3 1
2
0
2
3
1
