A16533. Isla's Memory Thresholds

我希望有一天，你能与那个你珍惜的人重逢。

—— Plastic Memories

在 Plastic 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$ 到 $r$ 个记忆碎片。任何时刻，当她当前持有的碎片的总大小不少于 $x$ 时，她会完全清空自己的记忆（不留下任何碎片）。你需要判断 Isla 清空记忆的次数，以及她最终持有的碎片大小之和。

每个测试包含多组测试数据。第一行包含测试组数 $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_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$。

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

令 $\texttt{cnt}$ 表示 Isla 清空记忆的次数，$\texttt{sum}$ 表示她当前持有碎片的总大小。

在第一个测试样例的第一个查询 $(l, r, x) = (1, 3, 10)$：

- 从 $\texttt{sum}=0$ 开始；
- 加上 $a_1=7 \Rightarrow \texttt{sum}=7$（仍小于 $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$（仍小于 $3$）；

因此，输出 $\texttt{cnt}=3$，$\texttt{sum}=2$。