题目描述

有一群人准备玩“Resistance”游戏。与传统规则不同的是，这次“好人”和“坏人”的人数都不固定。

对每个玩家 i，已知两项数值：

• 若他被分到好人阵营，会贡献 good[i]；
• 若他被分到坏人阵营，会贡献 bad[i]。

此外，还给出若干对玩家之间的友谊值。如果一对朋友被分在不同阵营，那么这段友谊就会被“破坏”，总价值中要减去其友谊值。

题目保证：任意一个既非空也非全集的玩家集合，与其补集之间至少存在一条友谊边。也就是说，友谊图是连通的。

一次分组方案的总价值定义为：

• 所有玩家在其所属阵营的贡献值之和，
• 减去所有“被破坏”的友谊值之和。

你的任务是求出最大可能总价值。

但事情还没结束：随着时间推移，有些玩家会离开，又会回来，因此需要不断重新计算当前在场玩家的最优分组价值。

初始时，N 名玩家全部在场。之后会发生 Q 次变化，变化类型如下：

• 1 x：编号为 x 的玩家返回（保证该玩家当前不在场）；
• 2 x：编号为 x 的玩家离开；
• 3：所有当前不在场的玩家全部返回；
• 4：编号从 1 到 floor(N/5) 的玩家全部离开。

对于每次变化后当前在场玩家集合，你需要按要求输出最优分组价值。

输入格式

第一行两个正整数 N, M，分别表示玩家数与已知友谊数。

第二行 N 个整数，表示每个玩家加入好人阵营时的贡献。

第三行 N 个整数，表示每个玩家加入坏人阵营时的贡献。

接下来 M 行，每行三个整数 x, y, t，表示玩家 x 与 y 之间的友谊值为 t。

接下来一行一个整数 Q，表示变化次数。

最后 Q 行描述变化：

• 若为类型 3 或 4，该行只包含一个整数；
• 若为类型 1 或 2，该行包含两个整数 type, x。

输出格式

• 第一行输出：初始时所有 N 名玩家都在场时的最优分组价值；
• 之后，对于每一次类型 1 或类型 2 的变化，在变化后输出当前在场玩家的最优分组价值；
• 对于类型 3 与类型 4，原题样例显示也会影响后续状态，但不要求在该行立即输出，输出规则以题面原文为准。为了兼容原题，建议实现时严格按照原始评测逻辑处理。

数据范围

• 2 <= N <= 1000
• 1 <= M <= 100000
• 0 <= Q <= 1500
• 所有贡献值与友谊值均为 0..1000 之间的整数

子任务

只有通过某个子任务中的全部测试，才能获得该子任务分数。

样例

输入

5 4
10 15 22 20 31
10 14 10 25 31
1 4 10
2 4 10
1 3 2
4 5 10
7
2 5
2 4
1 4
2 1
3
4
2 5

输出

100
69
47
69
61
61

说明

当所有玩家都在场时，最优分配方式是：第 3 名玩家属于好人阵营，其余玩家属于坏人阵营。此时总价值为：

10 + 14 + 22 + 25 + 31 - 2 = 100

其中减去的 2 来自玩家 1 与 3 被分在不同阵营时破坏的友谊。