Aurora 和 Bianca 非常喜欢 amaretti 饼干。今天，她们的爷爷烤了一大叠饼干。为了分饼干，她们发明了以下游戏。只要叠中还有饼干，她们就会重复以下步骤：

1. Aurora 选择一个整数 $X \ge 0$。

2. 接着，Bianca 选择一个整数 $Y \ge 0$，满足：

   • 剩余的饼干至少有 $Y$ 块，且
   • $Y \neq X$。
3. 然后，Aurora 吃掉最上面的 $Y$ 块饼干（如果 $Y = 0$ 则不吃）。
4. 最后，如果还有饼干剩余，Bianca 吃掉最上面的一块饼干。

当然，每个女孩都想尽可能多吃。叠中的每块饼干都有一个重量 $1 \le W_i \le 50$。一旦所有饼干都被吃完，每个女孩的幸福感就等于她在游戏中所吃的所有饼干的总重量。两个女孩都知道如何进行最优策略——她们每个人在游戏结束时总是做出能最大化自己幸福感的决策。

因为这个游戏太好玩了，她们现在想每天都玩！在接下来的 $Q$ 天里，她们的爷爷每天都会烤一叠数量相同的新饼干。为了让游戏更有趣，每天他会改变其中一块饼干的重量，而其他饼干的重量与前一天保持一致。

对于初始的饼干叠，以及每次修改之后，你需要确定每天游戏结束时 Bianca 的幸福感。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$，分别表示饼干叠中饼干的数量和修改的次数。饼干从上到下依次编号为 $0$ 到 $N - 1$。

第二行包含 $N$ 个整数 $W_0, W_1, \dots, W_{N-1}$，表示饼干的初始重量。

接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $P_i$ 和 $Z_i$，描述第 $i$ 次修改：爷爷将第 $P_i$ 块饼干的重量修改为 $Z_i$。换句话说，$W_{P_i}$ 的值修改为 $Z_i$。

输出格式

输出 $Q + 1$ 个整数，表示每次游戏后 Bianca 的幸福感。

数据范围

• $2 \le N \le 100\,000$。
• $0 \le Q \le 100\,000$。
• $1 \le W_i \le 50$（是的，amaretti 饼干非常轻！）。
• $0 \le P_i \le N - 1$ 且 $1 \le Z_i \le 50$。

子任务

你的程序将在分属于不同子任务的多个测试用例上进行测试。要获得某个子任务的分数，你必须正确解决其中包含的所有测试。

• 子任务 0 [0 分]：样例。
• 子任务 1 [8 分]：$Q = 0$ 且 $W_i = 1$。
• 子任务 2 [9 分]：$N \le 3$，$Q \le 5$。
• 子任务 3 [11 分]：在任何时间点，重量 $W_i$ 都是非递增的；换句话说，满足 $W_0 \ge W_1 \ge \dots \ge W_{N-1}$。
• 子任务 4 [13 分]：$N \le 100$，$Q \le 50$。
• 子任务 5 [18 分]：$N \le 20\,000$，$Q \le 50$。
• 子任务 6 [12 分]：$N \le 20\,000$，$Q \le 5000$。
• 子任务 7 [29 分]：无附加限制。

样例

输入格式 1

2 1
10 15
1 1

输出格式 1

10
1

输入格式 2

5 2
1 1 1 1 2
2 20
3 30

输出格式 2

3
4
24

输入格式 3

4 2
1 2 4 8
3 2
2 3

输出格式 3

7
4
4

输入格式 4

3 0
1 1 1

输出格式 4

1

输入格式 5

3 4
50 8 1
1 1
1 8
2 7
2 1

输出格式 5

8
1
8
8
8

说明

第一个样例。在第一天，饼干的重量为 $10$ 和 $15$。

• Aurora 选择 $X = 1$ 是最优的。然后，Bianca 选择 $Y = 0$ 并吃掉最上面的饼干。
• 在第二轮中，Aurora 选择 $X = 0$。Bianca 唯一的选择是 $Y = 1$。然后，Aurora 吃掉重量为 $15$ 的饼干，游戏结束。

在第二天，第 $1$ 块饼干的重量修改为 $1$，此时饼干的重量为 $[10, 1]$。

• Aurora 选择 $X = 0$ 是最优的。然后，Bianca 选择 $Y = 1$。Aurora 吃掉最上面的饼干，Bianca 吃掉剩下的一块。

游戏结束后 Bianca 的幸福感为 $1$。

第二个样例。饼干的初始重量从上到下为 $[1, 1, 1, 1, 2]$。

• Aurora 选择 $X = 0$ 是最优的。然后 Bianca 选择 $Y = 1$。Aurora 吃掉第一块饼干，Bianca 吃掉第二块。
• 在下一轮中，Aurora 选择 $X = 0$。然后 Bianca 选择 $Y = 2$。Aurora 吃掉接下来的两块饼干，Bianca 吃掉最后一块。游戏结束，Bianca 的总幸福感为 $3$。

在第一次修改后，重量为 $[1, 1, 20, 1, 2]$。

• 现在 Aurora 选择 $X = 2$ 是最优的。（如果她选择任何其他值，Bianca 都会选择 $Y = 2$，这样 Aurora 就吃不到中间的大饼干了。）作为对 Aurora 选择的回应，Bianca 选择 $Y = 0$ 并吃掉第一块饼干。剩余的饼干重量为 $[1, 20, 1, 2]$。
• 在第二轮中，Aurora 选择 $X = 1$，Bianca 选择 $Y = 0$。同样，Bianca 吃掉最上面的饼干。之后，剩余饼干的重量为 $[20, 1, 2]$。
• 在第三轮中，Aurora 选择 $X = 0$。Bianca 选择 $Y = 2$。之后，Aurora 吃掉重量为 $20$ 和 $1$ 的饼干，最后 Bianca 吃掉最后一块重量为 $2$ 的饼干。Bianca 吃掉的饼干总重量为 $1 + 1 + 2 = 4$。

在第二次修改后，重量为 $[1, 1, 20, 30, 2]$。如果两个女孩都采取最优策略，Bianca 会吃掉除重量为 $30$ 的饼干之外的所有饼干。