F. Пороги памяти Ислы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Я надеюсь, что однажды вы воссоединитесь с тем, кого вы цените.
— Пластиковые воспоминания

В мире Пластиковых воспоминаний Исла собирает $$$n$$$ фрагментов памяти. $$$i$$$-й фрагмент имеет размер $$$a_i$$$, и размеры являются невозрастающими, то есть $$$a_1 \ge a_2 \ge \cdots \ge a_n$$$.

Во время извлечения Исла обрабатывает фрагменты в диапазоне и сохраняет их размеры в буфер. Когда буфер достигает заданного порога $$$x$$$, он переполняется: одна капсула записывается, и буфер очищается до нуля.

Существует $$$q$$$ независимых запросов, каждый из которых описывается тройкой $$$(l,r,x)$$$. Для каждого запроса $$$x$$$ обозначает ёмкость памяти Ислы. Затем Исла поочередно берёт $$$i$$$-й фрагмент памяти для каждого $$$l \le i \le r$$$. В любой момент, если общий размер фрагментов, которые она в данный момент держит, составляет не менее $$$x$$$, она полностью очищает свою память (ничего не оставляя). Вам необходимо определить, сколько раз Исла очищает свою память и окончательную сумму размеров фрагментов, которые она держит.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 150,000$$$) — длина $$$a$$$ и количество запросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$. Гарантируется, что $$$a_1 \ge a_2 \ge \cdots \ge a_n$$$.

Затем следуют $$$q$$$ строк, каждая из которых содержит три целых числа $$$l$$$, $$$r$$$ и $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^9$$$) — запрос.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$150,000$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$150,000$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа для каждого запроса — количество раз, которое Исла очищает свою память, и окончательную сумму размеров фрагментов, которые она держит.

Пример
Входные данные
3
5 4
7 5 5 2 1
1 3 10
2 5 6
1 5 7
3 5 4
6 5
6 6 5 3 2 2
1 6 2
1 6 7
2 6 7
2 5 4
2 5 3
11 7
938412006 792864920 746880066 729862150 704473377 550436315 381392172 326088331 316506801 301443698 190862681
1 3 417253102
9 11 857592497
1 11 344359921
1 7 408760015
8 8 544749974
7 10 361090133
3 11 888178376
Выходные данные
1 5
1 3
2 3
1 3
6 0
2 4
2 0
3 0
3 2
3 0
0 808813180
9 0
6 381392172
0 326088331
2 301443698
3 492306379
Примечание

Пусть $$$\texttt{cnt}$$$ будет количеством раз, которое Исла очистила свою память, а $$$\texttt{sum}$$$ будет общей суммой размеров фрагментов, которые она держит.

В первом наборе входных данных, для первого запроса $$$(l, r, x) = (1, 3, 10)$$$:

  • начинаем с $$$\texttt{sum}=0$$$;
  • добавляем $$$a_1=7 \Rightarrow \texttt{sum}=7$$$ (всё ещё $$$ \lt 10$$$);
  • добавляем $$$a_2=5 \Rightarrow \texttt{sum}=12 \ge 10 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 1$$$;
  • добавляем $$$a_3=5 \Rightarrow \texttt{sum}=5$$$.

Таким образом, мы выводим $$$\texttt{cnt}=1$$$ и $$$\texttt{sum}=5$$$.

Во втором наборе входных данных, для пятого запроса $$$(l, r, x) = (2, 5, 3)$$$:

  • начинаем с $$$\texttt{sum}=0$$$;
  • добавляем $$$a_2=6 \Rightarrow \texttt{sum}=6 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 1$$$;
  • добавляем $$$a_3=5 \Rightarrow \texttt{sum}=5 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 2$$$;
  • добавляем $$$a_4=3 \Rightarrow \texttt{sum}=3 \ge 3 \Rightarrow \texttt{sum} \gets 0$$$, $$$\texttt{cnt} \gets 3$$$;
  • добавляем $$$a_5=2 \Rightarrow \texttt{sum}=2$$$ (всё ещё $$$ \lt 3$$$);
Таким образом, мы выводим $$$\texttt{cnt}=3$$$ и $$$\texttt{sum}=2$$$.