在世界上 可塑性记忆,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$$$ 逐一拾取第 $$$i$$$ 个内存片段。在任何时刻,如果她当前持有的碎片的总大小至少为$$$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$$$。
输出
对于每个测试用例,为每个查询输出两个整数——Isla 清除内存的次数以及她持有的片段大小的最终总和。
示例
输入复制
35 47 5 5 2 11 3 102 5 61 5 73 5 46 56 6 5 3 2 21 6 21 6 72 6 72 5 42 5 311 7938412006 792864920 746880066 729862150 704473377 550436315 381392172 326088331 316506801 301443698 1908626811 3 4172531029 11 8575924971 11 3443599211 7 4087600158 8 5447499747 10 3610901333 11 888178376
输出复制
1 51 32 31 36 02 42 03 03 23 00 8088131809 06 3813921720 3260883312 3014436983 492306379
注意
设 $$$\texttt{cnt}$$$ 为 Isla 清除记忆的次数,$$$\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$$$);