Добрый день, codeforces. Сегодня я хочу поделиться с вами одной задачей, которую я встретил в интернете и никак не могу решить, поэтому я решил обратиться к вам.
Задача
Ограничение времени: 3 секунды
Ограничение памяти: 256 мегабайт
Вам дан массив A из N натуральных чисел, а также вам даны Q запросов. Запросы бывают только одного типа: ? l r x — узнать сумму ⌊A[i] / x⌋, таким что (l <= i && i <= r) Ответьте на все эти запросы.

Входные данные
В первой строке входных данных задано число 1 <= N <= 100000 и 1 <= Q <= 2000000
Во второй строке вам даны n натуральных чисел 1 <= A[i] <= 20000
В строках с 3 по m + 2 строку даны запросы вида 1 <= l, r <= N и 1 <= x <= 1000000000
Нумерация массива идёт с одного.

Выходные файлы
Выведите ответ на каждый запрос в отдельной строке.

Примеры
Входные данные
10 5
10 5 1 3 10 14 15 8 19 11
1 10 2
5 7 100
2 3 2
4 7 3
9 10 1

Выходные данные
45
0
2
13
30

P.S.Разбора у данной задачи найти я не смог на сайте тоже нет.