在著名的 Oh-Suit-United 锦标赛中,两支队伍正在为争夺珍贵的胡椒点大奖而展开对决。
第一队由$$$n$$$玩家组成,第二队由$$$m$$$玩家组成。每个球员都有潜力:第一队中第 $$$i$$$ 球员的潜力为 $$$a_i$$$,第二队中第 $$$i$$$ 球员的潜力为 $$$b_i$$$。
比赛中,所有选手将按一定顺序上台。将会有一个计分装置,最初分配给一个整数$$$k$$$,它将用于评估所有玩家的表现。
所有玩家的分数将按照他们在舞台上出现的顺序分配。令当前玩家的潜力为$$$x$$$,前一个玩家的潜力为$$$y$$$($$$y$$$ 等于第一个玩家的$$$x$$$)。然后,将$$$x-y$$$加上计分器中的值,之后,如果计分器中的值变为负数,则该值将被重置为$$$0$$$。最后,玩家的分数被分配给计分设备上的当前值。团队的得分是其所有成员得分的总和。
作为一线队的疯狂球迷,内扎尔迫切希望一线队取得最大的胜利。他现在想知道第一队和第二队的分数最大相差多少。
正式来说,让第一队的得分为$$$score_f$$$,第二队的得分为$$$score_s$$$。 Nezzar 想要找到舞台上所有可能的玩家顺序中 $$$score_f - Score_s$$$ 的最大值。
然而,情况经常发生变化,并且会发生 $$$q$$$ 事件。事件分为三种类型:
- $$$1$$$ $$$pos$$$ $$$x$$$ — 将 $$$a_{pos}$$$ 更改为 $$$x$$$;
- $$$2$$$ $$$pos$$$ $$$x$$$ — 将 $$$b_{pos}$$$ 更改为 $$$x$$$;
- $$$3$$$ $$$x$$$ — 锦标赛以 $$$k = x$$$ 举行,Nezzar 希望您计算 $$$score_f - Score_s$$$ 的最大值。
你能帮助Nezzar回答第三类疑问吗?
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n,m \le 2 \cdot 10^5, 1 \le q \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$)。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \le b_i \le 10^6$$$)。
以下 $$$q$$$ 行包含语句中描述的事件描述,每行采用三种可能格式之一:
- $$$1$$$ $$$pos$$$ $$$x$$$ ($$$1 \le pos \le n$$$, $$$0 \le x \le 10^6$$$);
- $$$2$$$ $$$pos$$$ $$$x$$$ ($$$1 \le pos \le m$$$, $$$0 \le x \le 10^6$$$);
- $$$3$$$ $$$x$$$ ($$$0 \le x \le 10^6$$$)。
输出
对于第三种类型的每个查询,打印该查询的答案。
示例
输入 #1
3 4 3 1 2 7 3 4 5 6 3 5 1 1 10 3 5
输出 #1
-4 9
输入 #2
7 8 12 958125 14018 215153 35195 90380 30535 204125 591020 930598 252577 333333 999942 1236 9456 82390 3 123458 2 4 444444 3 123456 1 2 355555 3 123478 3 1111 2 6 340324 3 1111 2 8 999999 2 7 595959 3 222222 3 100
输出 #2
1361307 1361311 1702804 1879305 1821765 1078115 1675180
注意
在第一次测试的第一个查询中,锦标赛以 $$$k = 5$$$ 举行。最好这样安排球员(这里写的是他们的潜力):
$$$\underline{7}$$$、$$$3$$$、$$$5$$$、$$$4$$$、$$$6$$$、$$$\underline{1}$$$、$$$\underline{2}$$$(下划线数字是一线队球员的潜力)。
选手个人得分按出场顺序编号为:
- $$$\max(5 + (7 - 7), 0) = 5$$$ 对于 $$$\underline{1}$$$-st 玩家;
- $$$\max(5 + (3 - 7), 0) = 1$$$ 对于第 $$$2$$$ 位玩家;
- $$$\max(1 + (5 - 3), 0) = 3$$$ 对于第 $$$3$$$-rd 玩家;
- 第 $$$4$$$ 位玩家的 $$$\max(3 + (4 - 5), 0) = 2$$$;
- 第 $$$5$$$ 位玩家的 $$$\max(2 + (6 - 4), 0) = 4$$$;
- $$$\max(4 + (1 - 6), 0) = 0$$$ 对于第 $$$\underline{6}$$$ 玩家;
- 第 $$$\underline{7}$$$ 位玩家的 $$$\max(0 + (2 - 1), 0) = 1$$$。
因此,$$$score_f = 5 + 0 + 1 = 6$$$ 和 $$$score_s = 1 + 3 + 2 + 4 = 10$$$。分数差异为 $$$6 - 10 = -4$$$。可以证明,这是最大可能的分数差。