背景

有个地方真实存在，有着复眼能看到的色彩。

在人们无数次沉没里，怎么还有条船不远万里。

题目描述

给定一个长度为 $n$ 的非负整数序列 $A_1, \ldots, A_n$ 以及两个长度为 $k$ 的正整数序列 $B_1, \ldots, B_k$ 和非负整数序列 $C_1, \ldots, C_k$。

你使用的 sʍopuᴉʍ 系统的画图软件有 $k$ 种颜色 $1\sim k$。你需要为 $n$ 个元素都涂上一种颜色，使得颜色 $i$ 的出现次数恰好为 $B_i$。

对于涂上了第 $i$ 种颜色的元素，值同时加上 $C_i$。

经过上述操作后会得到新的序列 $A'$，你想知道序列 $A'$ 可能的最小极差是多少（极差的定义为整个序列的最大值减去最小值的值）。

这实在太困难了，所以你的 sʍopuᴉʍ 系统共 $Q$ 次发生 UB 错误，把你的序列 $A$ 改掉了！第 $i$ 次会把 $A_{x_i}$ 改为 $v_i$。在你解决完问题后你会发现序列被修改了，所以你按下了 Ctrl+Z 撤销这次修改。

但是这很有趣！你需要把每次修改后的答案输出。

输入格式

第一行，三个正整数 $n,k,q$，含义见题目描述。

第二行，$n$ 个非负整数 $A_1, \ldots, A_n$。

第三行，$k$ 个正整数 $B_1, \ldots, B_k$。

第四行，$k$ 个非负整数 $C_1, \ldots, C_k$。

接下来 $q$ 行，每行两个整数 $x_i, v_i$，表示将 $A_{x_i}$ 改为 $v_i$。修改之间独立。

输出格式

共 $q$ 行，每行一个非负整数，表示修改后可能的最小极差。

5 4 5
8 4 4 4 5
1 1 2 1
5 4 6 4
4 8
4 3
4 5
5 8
1 2

2
3
3
3
2

提示

【样例解释 #1】

• 第一次修改后序列为：$\langle 8,4,4,8,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+6}},8{\color{red}{{}+4}},5{\color{red}{{}+5}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(5{\color{red}{{}+5}})=2$。

• 第二次修改后序列为：$\langle 8,4,4,3,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},3{\color{red}{{}+6}},5{\color{red}{{}+4}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(3{\color{red}{{}+6}})=3$。

• 第三次修改后序列为：$\langle 8,4,4,5,5\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},5{\color{red}{{}+4}},5{\color{red}{{}+6}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(4{\color{red}{{}+5}})=3$。

• 第四次修改后序列为：$\langle 8,4,4,4,8\rangle$，可行的操作是 $\langle 8{\color{red}{{}+4}},4{\color{red}{{}+6}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},8{\color{red}{{}+4}}\rangle$，最小极差为 $8{\color{red}{{}+4}}-(4{\color{red}{{}+5}})=3$。

• 第五次修改后序列为：$\langle 2,4,4,4,5\rangle$，可行的操作是 $\langle 2{\color{red}{{}+6}},4{\color{red}{{}+6}},4{\color{red}{{}+5}},4{\color{red}{{}+4}},5{\color{red}{{}+4}}\rangle$，最小极差为 $4{\color{red}{{}+6}}-(2{\color{red}{{}+6}})=2$。

【样例 #2】

见选手目录下的 $\textbf{\textit{register/register2.in}}$ 与 $\textbf{\textit{register/register2.ans}}$。

该样例满足测试点 $1$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{register/register3.in}}$ 与 $\textbf{\textit{register/register3.ans}}$。

该样例满足测试点 $2\sim 5$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{register/register4.in}}$ 与 $\textbf{\textit{register/register4.ans}}$。

该样例满足测试点 $6\sim 8$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{register/register5.in}}$ 与 $\textbf{\textit{register/register5.ans}}$。

该样例满足测试点 $9\sim 11$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{register/register6.in}}$ 与 $\textbf{\textit{register/register6.ans}}$。

该样例满足测试点 $12\sim 20$ 的约束条件。

【数据范围】

本题共 $20$ 个测试点，每个 $5$ 分。

对于所有测试数据，保证：

• $1\le k\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$；
• $1\le x_i\le n$；
• $0\le A_i,C_i,v_i \le 5\times 10^5$；
• $1\le B_i\le 5\times 10^5$；
• $\sum B_i=n$。

::cute-table{tuack}

特殊性质 A：$A_i,C_i,v_i\le 8$。
特殊性质 B：$k=2$。
特殊性质 C：$C_i\le 1$。