MLE 得到了 QAQ 的真传，但 QAQ 为了检验 MLE 智商是否可以真正领悟，于是出了这一道题：给出 n 个数的序列，先把每个数逆序（如 120 变为 21，123 变为 321），将会产生 n 个新数，我们把它称作序列 A。

之后对序列 A 中的 n-1 个数进行 q 次操作，每次操作将会把序列 A 上的某个数替换成另一个数，并询问序列 A 中任取连续的一段数，如何取才能使这段数的和最大，请你输出最大值。

输入数据有多组（数据组数不超过 100）。

对于每组数据：

• 第一行输入 n, q (1 <= n <= 10000, 1 <= q <= 100) 分别表示数字个数和操作次数
• 接下来的一行输入 n 个正整数，最大不超过 10000
• 接下来的 q 行，每行输入 2 个整数，分别为要替换的数的位置 xi (1 <= xi <= n) 和要修改的值 yi (-10000 <= yi <= 10000)

当 n = 0 时输入结束。

对于每组数据第一行输出 "Case #x:" (不包括引号，冒号后无空格)，x 表示当前为第几组数据。之后对应 q 次操作每次操作输出一行，表示查询的答案。

5 2
1 2 3 4 5
2 -5
2 5
3 3
45 12 32
3 -5
1 5
2 10
0

Case #1:
12
18
Case #2:
75
26
15

请大家仔细核对 "Case #x:"，建议复制样例输出的模式以防输出时不符合题目要求而导致的 Wrong Answer。