题目描述

有 $n$ 个独立的车厢在铁轨上，编号从 $1$ 到 $n$。车厢没有连接在一起。车厢向左移动，所以编号为 $1$ 的车厢领先于它们所有的车厢。

第 $i$ 个车厢有自己的引擎，可以将车厢加速到 $a_i$ 公里/小时，但是车厢不能比前面的车厢跑得更快。详见样例。

所有车厢同时开始向左移动，它们自然地形成了一些列火车。我们将由相同速度的连续移动的车厢称为一列火车。

例如，有 $n=5$ 辆车厢和数组 $a=[10,13,5,2,6]$。那么车厢的最终速度将是 $[10,10,5,2,2]$。相应地，将形成 $3$ 列火车。

还有消息说某个引擎已经损坏了：

消息 k d 表示第 $k$ 辆车的速度降低了 $d$（即车厢的最大速度发生了变化 $a_k=a_k−d$ ）。

消息逐个到达，处理下一条消息时会考虑所有先前消息的更改。

在每个消息之后，确定形成的火车数量。

输入格式

输入数据的第一行包含一个整数 $t(1≤t≤10^4)$ — 测试用例的数量。

其后是每个测试用例的描述。

每个测试用例的第一行为空行。

测试用例的第二行包含两个整数 $n$ 和 $m$ $(1≤n,m≤10^5)$ — 车厢数量和减速消息数量。

第三行包含 $n$ 个整数: $a_1,a_2,…,a_n (0≤a_i≤10^9)$ — 数字 $a_i$ 表示第 $i$ 辆车可以达到 $a_i$ 公里/小时的速度。

接下来的 $m$ 行包含两个整数 $k_j$ 和 $d_j(1≤k_j≤n, 0≤d_j≤a_{k_j})$ — 这是第 $k_j$ 辆车速度减慢了 $d_j$。换句话说，它的最大速度 $a_{k_j}=a_{k_j}−d_j$ 有所变化。请注意，在任何时候，每个车厢的速度都是非负的。换句话说，$a_i≥s_i$，其中 $s_i$ 是所有 $k_j=i$ 的 $d_j$ 的和。

保证 $n$ 所有测试用例的总和不超过 $10^5$。同样，保证 $m$ 所有测试用例的总和不超过 $10^5$。

输出格式

打印 $t$ 行。每行打印相应测试用例的答案。

对于每个测试用例，打印 $m$ 个数字：每条消息后形成的火车数量。

测试样例

3

4 2
6 2 3 7
3 2
4 7

5 4
10 13 5 2 6
2 4
5 2
1 5
3 2

13 4
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
6 222
7 233
5 117

3 4 
4 4 2 3 
5 6 6 5

样例说明

针对第一个测试用例：

初始数组 $a=[6,2,3,7]$。

第一条消息后，数组 $a=[6,2,1,7]$。因此，车厢的速度为 $[6,2,1,1]$，将形成 $3$ 节火车。

第二条消息后，数组 $a=[6,2,1,0]$。因此，车厢的速度为 $[6,2,1,0]$，将形成 $4$ 节火车。

针对第二个测试用例：

初始数组 $a=[10,13,5,2,6]$。

第一条消息后，数组 $a=[10,9,5,2,6]$。因此，车厢的速度相同：$[10,9,5,2,2]$，将形成 $4$ 节火车。

第二条消息后，数组 $a=[10,9,5,2,4]$。因此，车厢的速度为 $[10,9,5,2,2]$，将形成 $4$ 节火车。

第三条消息后，数组 $a=[5,9,5,2,4]$。因此，车厢的速度为 $[5,5,5,2,2]$，将形成 $2$ 节火车。

第四条消息后，数组 $a=[5,9,3,2,4]$。因此，车厢的速度为 $[5,5,3,2,2]$，将形成 $3$ 节火车。