背景

::::info[引言：其之四] :::align{center} $\textbf{旧忆再染新绪，\color{gold}幻梦}\textbf{长存。}$ ::: ::::

门扉缓缓打开，一线天光洒入。

——门外的晴空，湛蓝一片。

不知何时，雨已经停了。

博丽的巫女，从秘神的国度中轻巧地跃出，在蓝天下自由地翱翔。

忽然间，她像察觉到了什么似的，在半空中来了一个急刹车。常伴其身的四枚阴阳玉，也顺从着主人的意愿放缓了速度。

紧接着——

一道隙间绽裂，老谋深算的贤者手执阳伞飘出；
一扇门扉张开，玩世不恭的贤者环抱双臂跳出；
一只巨鹰飞过，和蔼温柔的贤者背着双手走出。

“畜生界，月之都，消失的所有权……”最像妖怪的妖怪如是说；
“……异变的起始，异变的结局，相较于过往愈发沉重。”绝对的究极秘神如是说；
“——一直以来辛苦了，灵梦。”独臂有角的仙人如是说。

“还记得过去的那些，轻松愉快的异变吗？”
“为了挡住太阳而发动的异变，为了赏樱而发动的异变，每六十年一次自然而然地发动的异变。”
“那些胡闹一般的、孩子气的异变。”

“那样的感觉，有多久没有体验过了？”
“那些宴会上的觥筹交错，新的朋友与新的去处？”
“灵梦，你难道不怀念过去那无忧无虑的时光吗？”

“我们为你准备了一个惊喜。”
“我们为你准备了一个惊喜。”
“我们为你准备了一个惊喜。”

——三位贤者异口同声。

“一个小小的奇迹。”八云紫打开了折扇。
“一方小小的天地。”摩多罗·隐岐奈倚着背后的门。
“我们就在这里，望你来，伴你去。”茨木华扇右臂的绷带散落了，其下空无一物。

“在这众神眷恋的幻想乡中……”
“在这永不终结的幻梦中……”
“谜底就在你的心里。”

“去痛快的玩上一场吧，正如往常一般。”
“昔日的友人，幻想的住民……”
“我们都在这里等你。”

一阵清风拂过，博丽灵梦不由得眨了眨眼。就在同一时刻，面前的三人同时销声匿迹——再一次。

然而，明明失去了踪影，贤者们的声音，仍然清晰可辨。

“我亲爱的灵梦哟……”
“顺着记忆的河流往回走吧……”
“……去回想，那命名决斗法案的理念，那符卡规则的初衷——”

$$\textbf{\color{purple}“其一，妖怪能轻松发动异变。”}$$ $$\textbf{\color{orange}“其二，人类能轻松解决异变。”}$$ $$\textbf{\color{pink}“其三，否定完全的实力主义。”}$$

——话语戛然而止。

最后的空缺，异变的谜底，留给了博丽灵梦自己。

于是，乐园的巫女，望向万里无云的天空，望向天边垂吊的彩虹。

……她早已知晓答案。

$$\textbf{\color{red}“其四，没有东西能胜过美丽与思念。”}$$

“……紫，摩多罗，华扇……”

“……啊啊。”

“真的，万分感谢。”

仰头望天，回予一个淡然的微笑。

题目描述

原始题面

在与三位贤者交谈时，博丽灵梦得知，自己身处茨木华扇临时制造的仙界中。

与此同时，三位贤者还与过去历次异变的黑幕们商定，将她们也请进了这片仙界。

当然，为了最大程度的保留惊喜感，这些幕后的商谈都是背着各位异变解决者们——尤其是博丽巫女——进行的。

贤者们的目的是，人为地制造一场异变，借此机会让幻想乡中的大家体会到同过去一样的单纯的欢乐；同时，也有着“让近期接连参与了多项危及幻想乡的大事件的异变解决者们，得以拥有休憩的余暇”的意图。

“也就是说，果然还是要打弹幕战才能玩个尽兴，这样的考量吗。”

灵梦耸了耸肩——谁会不喜欢来上一场刺激、欢乐而又兼具美感的弹幕战呢？

于是，巫女猛地加速，向着雨后初晴的天空飞去。

放眼望去，这片仙界中有着 $n$ 个令博丽灵梦感到可疑的区域，$m$ 条道路将这些区域连在了一起。

灵梦觉得这些地方可疑，并不是没有原因的——如果观察的仔细一点就会发现，每一处被她重点关注的区域，都能发现些许人影。粗略估计一下人数的话，每片区域大概有 $a_i$ 个人吧。

做完了基本的信息统计之后，乐园的巫女就要开始活动了。在接下来的 $t$ 个时刻中，她会进行如下三种行动：

• 锁定 $q$ 个区域，并尝试通过攻占与之不同的另一个区域来使得这 $q$ 个区域之间不能连通。灵梦想要知道，她所攻占的区域中最少的人数。如果不存在这样的区域，回答 -1。

• 锁定 $q$ 个区域，并尝试通过攻占与之不同的另一个区域来使得这 $q$ 个区域之间不能连通。灵梦想要知道，所有可能被她当做目标的区域的人数之和。如果不存在这样的区域，回答 -1。

• 博丽灵梦观察到，某一片区域的人数发生了变动（有些人凭空多出来/消失掉了，似乎是在幻想乡与这个小仙界间来来往往）。

当然，前两种行动彼此之间是独立的（被攻占的区域的人们会在博丽灵梦离开后回到这里）。

形式化题意

有一张 $n$ 个点，$m$ 条边的无向连通图，点有点权。

接下来有 $t$ 个事件发生，每个事件是以下三个中的一个：

• 给定 $q$ 个关键点，你需要删掉一个非关键点使得 $q$ 个关键点之间不连通。问删除的这个点的点权最小是多少。如果不存在这样的点，回答 -1。

• 给定 $q$ 个关键点，你需要删掉一个非关键点使得 $q$ 个关键点之间不连通。问所有可以删除的点的点权之和。如果不存在这样的点，回答 -1。

• 改变某个点的点权。

询问之间互相独立，询问不改变图的结构。

一张图的给定若干个点之间不连通，当且仅当给定的某两个点之间不存在路径。

输入格式

输入的第一行有两个整数 $n,m$，表示区域个数与道路条数。

第二行有 $n$ 个整数 $a_i$，表示第 $i$ 个区域原有的人数。

接下来 $m$ 行，每行两个整数 $x,y$，代表第 $x$ 个区域和第 $y$ 个区域之间存在道路。

第 $m+3$ 行一个整数 $t$，表示灵梦的行动次数。

接下来 $t$ 行，每行第一个整数 $opt$ 表示行动类型。

若 $opt=1$ 或 $opt=2$，接下来输入一个数 $q$，再接下来输入 $q$ 个数 $d_i$，表示被灵梦锁定的 $q$ 个点。

若 $opt=3$，接下来输入两个数 $u,k$，表示第 $u$ 个区域的人数变为了 $k$。

输出格式

对于每一次 $opt=1$ 或 $opt=2$ 的行动，输出一行一个数，表示本次行动对应的答案。

特别地，如果对于某一次行动，满足条件的区域不存在，那么输出 -1 即可。

6 7
3 6 7 1 4 2
1 2
4 3
1 5
3 6
3 1
2 3
1 4
9
1 2 5 6
2 2 5 6
1 4 2 3 5 6
2 4 2 3 5 6
3 1 9
1 4 2 3 5 6
2 4 2 3 5 6
1 2 5 6
2 2 5 6

3
10
3
3
9
9
7
16

6 7
2 2 1 3 3 4
1 3
2 4
3 5
1 2
4 6
4 5
1 5
3
2 2 3 6
2 2 1 2
1 2 5 2

3
-1
-1

提示

数据范围

本题采用捆绑测试。

• Subtask $1$（$15\ \text{pts}$）：$1 \le n,m,t \le 100$，保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $100$。
• Subtask $2$（$15\ \text{pts}$）：$1 \le n,m,t \le 1000$。保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $1000$。
• Subtask $3$（$15\ \text{pts}$）：$1 \le n,m,t \le 50000$，$m=n-1$，且每个区域连接的道路数量不超过 $2$ 条。
• Subtask $4$（$15\ \text{pts}$）：$1 \le n,m,t \le 50000$，$m=n-1$。
• Subtask $5$（$20\ \text{pts}$）：$1 \le n,m,t \le 50000$。
• Subtask $6$（$20\ \text{pts}$）：无特殊限制。

对于所有数据：

• $1 \le n \le 10^5$。
• $n-1 \le m \le 2 \times 10^5$。
• 保证任何一个区域可以通过若干条道路到达其他任何一个区域。
• $1 \le a_i \le 10^5$。
• $1 \le t \le 10^5$。
• 对于 $opt=1$ 或 $opt=2$ 的行动，$1 \le q \le n$，$1 \le d_i \le n$，保证所有 $opt=1$ 或 $opt=2$ 的行动 的 $q$ 之和不超过 $2 \times 10^5$。
• 对于 $opt=3$ 的行动，$1 \le u \le n$，$1 \le k \le 10^5$。