You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

视界不现，巡航欲见。

题目背景

小时候，每天晚上邹锦舒的妈妈都会用望远镜给邹锦舒看一闪一闪的月亮。可现在，因为城市污染太严重了，邹锦舒看不见月亮。多怀念小时候的时光啊......

有一天，邹锦舒睡觉的时候，又梦见了小时候那美丽的月亮一闪一闪，周围有群星点缀，好漂亮......

可好景不长，邹锦舒被他的妈妈叫醒去上学了。

题目描述

邹锦舒很不舍，于是开始模拟起月亮的闪烁值。

月亮的初始闪烁值为 $x$，周围一共有 $n$ 颗星星，第 $i$ 颗星星的闪烁值为 $y_i$。每一颗星星都会和月亮形成一个整体。换句话说，第 $i$ 个整体的闪烁值为 $x+y_i$。现在有三种可能：

1. 月亮的闪烁值变为 $a$。
2. 把有着最大闪烁值的星星的闪烁值变成 $b$。
3. 把有着最小闪烁值的星星的闪烁值变成 $c$。

请帮邹锦舒算出，每一次操作后，最大的整体闪烁值是多少。

输入格式

第一行两个整数 $n$ 和 $x$，表示星星的总数和月亮的闪烁值。

第二行 $n$ 个整数，表示每一个星星的闪烁值。

第三行一个整数 $t$，表示操作的总数。

接下来 $t$ 行，首先一个整数 $op$，表示操作的类型（即为上文的 $1$ 或 $2$ 或 $3$）。

然后是一个整数 $a$ 或 $b$ 或 $c$，具体描述见上。

输出格式

$t$ 行，每行一个整数，表示一颗星星和月亮的总和的最大值。

3 5
1 2 3
3
2 1
1 3
3 10

7
5
13

提示

认为时间复杂度正确但只有暴力分的请使用更快的输入输出方式

现在有 $3$ 颗星星，闪烁值分别为 $\{1,2,3\}$。

第一次，将有着最大闪烁值的星星，也就是第三颗星星的闪烁值改为 $1$，也就是变成了 $\{1,2,1\}$。此时，最大的闪烁值应为第二颗星星加上月亮，也就是 $2+5=7$。

第二次，将月亮的闪烁值更改为 $3$，此时星星的所有闪烁值是 $\{1,2,1\}$ 最大的闪烁值为 $2+3=5$。

第三次，将有着最小闪烁值的星星，也就是第一颗星星的闪烁值改成 $10$，也就是变成了 $\{10,2,1\}$。此时，最大的闪烁值应为第二颗星星加上月亮，也就是 $10+3=13$。如果有多个相同的最大/最小，我们只更改其中的第一个。

特殊性质 $\tt{A}$：保证只有 $1$ 操作。

特殊性质 $\tt{B}$：保证只有 $2$ 操作。

特殊性质 $\tt{C}$：保证只有 $3$ 操作。

你可能需要一些更加快速的读入方式。