At the main street of Byteland, there will be built $n$ skyscrapers, standing sequentially one next to other. If look leftside right, sequence of their height will be $a_1, a_2, \\dots, a_n$.
Initially the street is empty, every skyscraper's height is $0$. Hamster is the leader of the construction team. In each stage, Hamster can select a range $[ l, r ]$, then the team will work on this range. Specifically, assume the height sequence is $h_1, h_2, \\dots, h_n$, then $h_l, h_{l + 1}, \\dots, h_r$ will increase by $1$ during this stage. When $h_i = a_i$ holds for all $i in [ 1, n ]$, the project will be closed.
The plan may be changed for many times. There will be $m$ events of $2$ kinds below:
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.
In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of skyscrapers and events.
In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 100000)$.
For the next $m$ lines, each line describes an event.
It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.
For each query event, print a single line containing an integer, denoting the answer.
## Input
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of skyscrapers and events.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 100000)$.For the next $m$ lines, each line describes an event.It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.
## Output
For each query event, print a single line containing an integer, denoting the answer.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ be the number of monsters.
- Let $ M_k = \{(HP_i, ATK_i) \mid i \in \{1, \dots, n_k\}\} $ be the set of monsters, where $ HP_i $ is the health point and $ ATK_i $ is the attack value of the $ i $-th monster.
**Constraints**
1. $ 1 \le T \le 10^3 $
2. For each test case $ k $:
- $ 1 \le n_k \le 10^5 $
- $ 1 \le HP_i, ATK_i \le 10^5 $ for all $ i \in \{1, \dots, n_k\} $
3. $ \sum_{k=1}^T n_k \le 10^6 $
**Objective**
Minimize the total damage suffered by the hero, defined as:
$$
\sum_{t=1}^T \left( \sum_{\substack{\text{alive monsters } i \\ \text{at second } t}} ATK_i \right)
$$
where at each second:
- The hero takes damage equal to the sum of $ ATK_i $ over all alive monsters.
- Then, the hero chooses one monster $ i $ to attack, dealing $ c_i $ damage to it, where $ c_i $ is the number of times monster $ i $ has been attacked so far (starting at 1).
- Monster $ i $ dies when cumulative damage to it $ \ge HP_i $.
The goal is to find the **minimum total damage** the hero must take over all seconds until all monsters are dead, by optimally choosing the order of attacks.