В знаменитом турнире Oh-Suit-United две команды играют друг против друга, борясь за главный приз.
Первая команда состоит из \(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 ответить на запросы третьего типа?
Выходные данные
Для каждого запроса третьего типа выведите ответ на этот запрос.
Примечание
В первом запросе первого примера турнир будет проводиться с \(k = 5\). Будет оптимально расположить игроков в следующем порядке (здесь будут записаны их потенциалы):
\(\underline{7}\), \(3\), \(5\), \(4\), \(6\), \(\underline{1}\), \(\underline{2}\) (подчеркнутые числа это потенциалы игроков из первой команды).
Личные очки игроков, пронумерованных в порядке, в котором они выступают:
- \(\max(5 + (7 - 7), 0) = 5\) для \(\underline{1}\)-го игрока;
- \(\max(5 + (3 - 7), 0) = 1\) для \(2\)-го игрока;
- \(\max(1 + (5 - 3), 0) = 3\) для \(3\)-го игрока;
- \(\max(3 + (4 - 5), 0) = 2\) для \(4\)-го игрока;
- \(\max(2 + (6 - 4), 0) = 4\) для \(5\)-го игрока;
- \(\max(4 + (1 - 6), 0) = 0\) для \(\underline{6}\)-го игрока;
- \(\max(0 + (2 - 1), 0) = 1\) для \(\underline{7}\)-го игрока.
Поэтому \(score_f = 5 + 0 + 1 = 6\) и \(score_s = 1 + 3 + 2 + 4 = 10\). Разница между количествами очков команд равна \(6 - 10 = -4\). Можно доказать, что это максимально возможная разница между количествами очков команд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 3
1 2 7
3 4 5 6
3 5
1 1 10
3 5
|
-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
|
1361307
1361311
1702804
1879305
1821765
1078115
1675180
|