夜世界

Problem Description

你来到了夜世界，这是一个神奇的地方，这里有金矿、哥布林、时光钟楼。 很幸运，夜世界的领主赏赐给你 $n$ 座排成一行的金矿，同时要求你在这里停留 $m$ 天，每座金矿有一个属性 $a_i$，代表该金矿一天产出的金币数量，但是，每座金矿中都潜伏着一只哥布林，每只哥布林都有一个属性 $b_i$，代表这只哥布林的贪婪值。 每天夜晚，你将从第 $1$ 座金矿走到第 $n$ 座金矿，每走过一座金矿，以下两件事情依次发生：

• 你将获得此座金矿当天产出的金币；
• 潜伏在此座金矿中的哥布林露出了爪牙，向你索要与它贪婪值相等的金币，如果你没有这么多金币，那你只能将自己所有的金币都交给它，随后它看你穷得可怜，会放你离开。 受到神秘力量的影响，每天早晨都会发生以下某一事件：
• 第 $x$ 座金矿一天产出的金币数量变为 $y$，修改是持久的；
• 第 $x$ 座金矿中潜伏的哥布林的贪婪值变为 $y$，修改是持久的；
• 时光钟楼显灵了！夜世界的状态被回溯到了第 $x$ 天！这意味着 $a,b$ 数组的状态将回退至与第 $x$ 天夜晚一致，初始给出的 $a,b$ 数组表示第 $0$ 天夜晚的状态；
• 有 $k$ 座金矿中潜伏的哥布林变得穷凶极恶，当天夜晚，它们将不再向你索要与它们贪婪值相等的金币，若你目前拥有 $sum$ 枚金币，它们将向你索要 $\lceil \frac{sum}{2} \rceil$ 枚金币，随后它们的神智清醒，不再穷凶极恶，但是你仍然很害怕，并希望知道当天夜晚你总共会交给哥布林多少金币，你需要打印这个值。

Input

第一行包含一个整数 $T$，表示测试数据的组数，$1 \leq T \leq 10$。 对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$，分别表示金矿的数量和你需要在夜世界停留的天数； 第二行包含 $n$ 个整数 $a_1, \thinspace a_2, \thinspace a_3, \thinspace \dots, \thinspace a_n \thickspace (0 \leq a_i \leq 1e9)$，表示每座金矿一天产出的金币数量； 第三行包含 $n$ 个整数 $b_1, \thinspace b_2, \thinspace b_3, \thinspace \dots, \thinspace b_n \thickspace (0 \leq b_i \leq 1e9)$，表示每座金矿中潜伏的哥布林的贪婪值； 接下来 $m$ 行，第 $i$ 行按如下格式给出一个操作：

• $1 \thickspace x \thickspace y: \thickspace$ 第 $x$ 座金矿一天产出的金币数量变为 $y$；
• $2 \thickspace x \thickspace y: \thickspace$ 第 $x$ 座金矿中潜伏的哥布林的贪婪值变为 $y$；
• $3 \thickspace x: \thickspace$ 夜世界的状态被回溯到了第 $x \thickspace (0 \leq x < i)$ 天；
• $4 \thickspace k: \thickspace$ 随后给出 $k \thickspace (k \ge 0)$ 个严格递增的金矿的位置，潜伏在这些金矿中的哥布林变得穷凶极恶。 数据保证：$\sum n \leq 2e5$，$\sum m \leq 2e5$，$\sum k \leq 2e5$。

Output

对于所有操作 $4$，你需要打印出当天夜晚你总共会交给哥布林多少金币。

Sample Input

1
4 5
1 9 10 8
2 4 2 4
2 2 6
2 1 9
1 3 20
3 1
4 2 2 4

Sample Output

18

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）