CF1477E.Nezzar and Tournaments

In the famous Oh-Suit-United tournament, two teams are playing against each other for the grand prize of precious pepper points.

The first team consists of $n$ players, and the second team consists of $m$ players. Each player has a potential: the potential of the $i$-th player in the first team is $a_i$, and the potential of the $i$-th player in the second team is $b_i$.

In the tournament, all players will be on the stage in some order. There will be a scoring device, initially assigned to an integer $k$, which will be used to value the performance of all players.

The scores for all players will be assigned in the order they appear on the stage. Let the potential of the current player be $x$, and the potential of the previous player be $y$ ($y$ equals $x$ for the first player). Then, $x-y$ is added to the value in the scoring device, Afterwards, if the value in the scoring device becomes negative, the value will be reset to $0$. Lastly, the player's score is assigned to the current value on the scoring device. The score of a team is the sum of the scores of all its members.

As an insane fan of the first team, Nezzar desperately wants the biggest win for the first team. He now wonders what is the maximum difference between scores of the first team and the second team.

Formally, let the score of the first team be $score_f$ and the score of the second team be $score_s$. Nezzar wants to find the maximum value of $score_f - score_s$ over all possible orders of players on the stage.

However, situation often changes and there are $q$ events that will happen. There are three types of events:

• $1$ $pos$ $x$ — change $a_{pos}$ to $x$;
• $2$ $pos$ $x$ — change $b_{pos}$ to $x$;
• $3$ $x$ — tournament is held with $k = x$ and Nezzar wants you to compute the maximum value of $score_f - score_s$.

Can you help Nezzar to answer the queries of the third type?

在著名的“Oh-Suit-United”锦标赛中，两支队伍正为珍贵的“胡椒点数”（pepper points）这一大奖展开对决。

第一支队伍由 $n$ 名选手组成，第二支队伍由 $m$ 名选手组成。每名选手均有一个“潜力值”：第一支队伍中第 $i$ 名选手的潜力值为 $a_i$，第二支队伍中第 $i$ 名选手的潜力值为 $b_i$。

在锦标赛中，所有选手将以某种顺序依次登上舞台。现场设有一台计分装置，其初始值为整数 $k$，用于评估所有选手的表现。

所有选手的得分将按其登台顺序依次计算。设当前选手的潜力值为 $x$，前一位选手的潜力值为 $y$（对于第一位选手，规定 $y = x$）。则将 $x - y$ 加到计分装置当前值上；随后，若计分装置的值变为负数，则立即将其重置为 $0$；最后，该选手的得分即为计分装置此时的值。一支队伍的总分等于其所有队员得分之和。

作为第一支队伍的狂热粉丝，Nezzar 极度渴望第一支队伍取得最大胜利。他现在想知道：第一支队伍与第二支队伍总分之差的最大可能值是多少？

形式化地，记第一支队伍的总分为 $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 回答所有第 3 类查询吗？

The first line contains three integers $n$, $m$, and $q$ ($1 \le n,m \le 2 \cdot 10^5, 1 \le q \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \le b_i \le 10^6$).

The following $q$ lines contain descriptions of events, described in the statement, each in one of the three possible formats:

• $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$).

第一行包含三个整数 $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$）。

For each query of the third type print the answer to this query.

对于每个第三种类型的查询，输出该查询的答案。

In the first query of the first test, the tournament is held with $k = 5$. It would be optimal to arrange players in such way (here their potentials are written):

$\underline{7}$, $3$, $5$, $4$, $6$, $\underline{1}$, $\underline{2}$ (underlined numbers are potentials of players that are from the first team).

The individual scores of players, numbered in the order of their appearance, are:

• $\max(5 + (7 - 7), 0) = 5$ for the $\underline{1}$-st player;
• $\max(5 + (3 - 7), 0) = 1$ for the $2$-nd player;
• $\max(1 + (5 - 3), 0) = 3$ for the $3$-rd player;
• $\max(3 + (4 - 5), 0) = 2$ for the $4$-th player;
• $\max(2 + (6 - 4), 0) = 4$ for the $5$-th player;
• $\max(4 + (1 - 6), 0) = 0$ for the $\underline{6}$-th player;
• $\max(0 + (2 - 1), 0) = 1$ for the $\underline{7}$-th player.

So, $score_f = 5 + 0 + 1 = 6$ and $score_s = 1 + 3 + 2 + 4 = 10$. The score difference is $6 - 10 = -4$. It can be proven, that it is the maximum possible score difference.

在第一个测试用例的第一个查询中，锦标赛的参数为 $k = 5$。此时，将选手按如下方式排列（括号内为其潜力值）是最优的：

$\underline{7}$, $3$, $5$, $4$, $6$, $\underline{1}$, $\underline{2}$（带下划线的数字表示第一支队伍选手的潜力值）。

按出场顺序编号的各位选手的个人得分如下：

• 第 $\underline{1}$ 位选手：$\max(5 + (7 - 7), 0) = 5$；
• 第 $2$ 位选手：$\max(5 + (3 - 7), 0) = 1$；
• 第 $3$ 位选手：$\max(1 + (5 - 3), 0) = 3$；
• 第 $4$ 位选手：$\max(3 + (4 - 5), 0) = 2$；
• 第 $5$ 位选手：$\max(2 + (6 - 4), 0) = 4$；
• 第 $\underline{6}$ 位选手：$\max(4 + (1 - 6), 0) = 0$；
• 第 $\underline{7}$ 位选手：$\max(0 + (2 - 1), 0) = 1$。

因此，$score_f = 5 + 0 + 1 = 6$，$score_s = 1 + 3 + 2 + 4 = 10$。分差为 $6 - 10 = -4$。可以证明，这是可能达到的最大分差。