题目描述

ws.hcl 有一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，并且一开始就给出一个常数 $k$，要求：

$$\max_{1 \le i < j \le n,, j - i \le k} {a_i + a_j}$$

但是 ws.hcl 觉得这根本难不倒你，于是 ws.hcl 给出了 $q$ 次修改操作，形式如 $a_x$ 修改为 $y$。 除了第一次修改前你需要输出答案之外，每次修改后你也都需要求出答案。

特别的，对于一部分测试点，我们有方法让你强制在线。

---

输入格式

输入的第一行包含四个正整数 $n, k, q, op$，分别表示序列长度、给定常数、操作次数、是否强制在线。

接下来一行 $n$ 个数，表示一开始的序列 $a_1 \sim a_n$。

接下来 $q$ 行，每行包含两个整数 $x$ 和 $y$，表示将第 $x$ 个数修改为 $y$。 当 $op = 1$ 时，你需要将输入中的所有数据异或上上一次输出的答案。

---

输出格式

输出 $q + 1$ 个数，表示每次的答案。

---

样例 #1

样例输入 #1

4 2 1 0
6 1 2 4
1 3

样例输出 #1

8
6

---

样例 #2

样例输入 #2

4 2 1 1
6 1 2 4
9 11

样例输出 #2

8
6

---

样例 #3

见附加文件 sequence3.in 和 sequence3.ans，该样例满足测试点 2～4 的限制。

---

样例 #4

见附加文件 sequence4.in 和 sequence4.ans，该样例满足测试点 9～11 的限制。

---

样例 #5

见附加文件 sequence5.in 和 sequence5.ans，该样例满足测试点 19～20 的限制。

---

数据范围

对于所有数据：

• $1 \le k, n, q \le 10^6$；
• $1 \le x' \le n$；
• $1 \le y' \le 10^9$。

其中 $x', y'$ 为每次操作的实际值。

---

测试点编号	$n \le$	$q \le$	$op =$
1	5000		1
2 ～ 4	$10^5$	$10^5$	0
5 ～ 8	$10^6$
9 ～ 11	$10^5$		1
12 ～ 14	$10^6$
15 ～ 18	$3 \times 10^5$
19 ～ 20	$10^6$