Олимпиадный тренинг

Задача . E. Слушаем музыку


Задача

Темы: Конструктив Структуры данных *3200

Обратите внимание на нестандартное ограничение по памяти.

Вы очень любите слушать музыку. В течение следующих 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.


Примеры
№Входные данныеВыходные данные
1 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

time 7000 ms
memory 64 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет