CF2173F.Isla's Memory Thresholds

I hope one day, you'll be reunited with the one you cherish.

— Plastic Memories

In the world of Plastic Memories, Isla is collecting $n$ memory fragments. The $i$-th fragment has size $a_i$, and the sizes are non-increasing, that is, $a_1 \ge a_2 \ge \cdots \ge a_n$.

During retrieval, Isla processes fragments on a range and stores their sizes into a buffer. Whenever the buffer reaches a given threshold $x$, it overflows: one capsule is recorded, and the buffer is cleared to zero.

There are $q$ independent queries, each described by a triple $(l,r,x)$. For each query, $x$ denotes Isla's memory capacity. Isla then picks up the $i$-th memory fragment one by one for each $l \le i \le r$. At any moment, if the total size of the fragments she is currently holding is at least $x$, she clears her memory completely (keeping nothing). You must determine how many times Isla clears her memory and the final sum of the size of the fragments she holds.

我希望终有一天，你能与你所珍视之人重逢。

——《塑料 Memories》

在《塑料 Memories》的世界中，Isla 正在收集 $n$ 个记忆碎片。第 $i$ 个碎片的大小为 $a_i$，且这些大小是非递增的，即满足 $a_1 \ge a_2 \ge \cdots \ge a_n$。

在检索过程中，Isla 会处理某一区间内的碎片，并将其大小存入一个缓冲区。每当缓冲区总和达到给定阈值 $x$ 时，缓冲区就会溢出：此时记录一个胶囊，缓冲区被清空为零。

共有 $q$ 个独立查询，每个查询由三元组 $(l,r,x)$ 描述。对每个查询，$x$ 表示 Isla 的记忆容量。Isla 将依次拾取下标满足 $l \le i \le r$ 的每一个记忆碎片。在任意时刻，若她当前所持碎片的总大小至少为 $x$，她便会完全清空自己的记忆（即不保留任何碎片）。你需要计算 Isla 清空记忆的次数，以及最终她所持碎片大小的总和。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 150,000$) — the length of $a$ and the number of queries.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of $a$. It is guaranteed that $a_1 \ge a_2 \ge \cdots \ge a_n$.

Then $q$ lines follow, each containing three integers $l$, $r$, and $x$ ($1 \le l \le r \le n$, $1 \le x \le 10^9$) — a query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $150,000$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $150,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output two integers for each query — the number of times Isla clears her memory and the final sum of the size of the fragments she holds.

对于每个测试用例，针对每个查询，输出两个整数——Isla 清空其记忆的次数，以及她所持有的碎片大小之和的最终值。

Let $\texttt{cnt}$ be how many times Isla has cleared her memory, and $\texttt{sum}$ be the total size of the fragments she is holding.

In the first test case, for the first query $(l, r, x) = (1, 3, 10)$:

• start with $\texttt{sum}=0$;
• add $a_1=7 \Rightarrow \texttt{sum}=7$ (still $ \lt 10$);
• add $a_2=5 \Rightarrow \texttt{sum}=12 \ge 10 \Rightarrow \texttt{sum} \gets 0$, $\texttt{cnt} \gets 1$;
• add $a_3=5 \Rightarrow \texttt{sum}=5$.

Thus, we print $\texttt{cnt}=1$ and $\texttt{sum}=5$.

In the second test case, for the fifth query $(l, r, x) = (2, 5, 3)$:

• start with $\texttt{sum}=0$;
• add $a_2=6 \Rightarrow \texttt{sum}=6 \ge 3 \Rightarrow \texttt{sum} \gets 0$, $\texttt{cnt} \gets 1$;
• add $a_3=5 \Rightarrow \texttt{sum}=5 \ge 3 \Rightarrow \texttt{sum} \gets 0$, $\texttt{cnt} \gets 2$;
• add $a_4=3 \Rightarrow \texttt{sum}=3 \ge 3 \Rightarrow \texttt{sum} \gets 0$, $\texttt{cnt} \gets 3$;
• add $a_5=2 \Rightarrow \texttt{sum}=2$ (still $ \lt 3$);

Thus, we print $\texttt{cnt}=3$ and $\texttt{sum}=2$.

令 $\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$。