F. Isla's Memory Thresholds
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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.

Example
Input
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
Output
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
Note

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$$$.