问题 B: 夜世界

你来到了夜世界，这是一个神奇的地方，这里有金矿、哥布林、时光钟楼。

很幸运，夜世界的领主赏赐给你 $n$ 座排成一行的金矿，同时要求你在这里停留 $m$ 天，每座金矿有一个属性 aiai，代表该金矿一天产出的金币数量，但是，每座金矿中都潜伏着一只哥布林，每只哥布林都有一个属性 bibi，代表这只哥布林的贪婪值。

每天夜晚，你将从第 $1$ 座金矿走到第 $n$ 座金矿，每走过一座金矿，以下两件事情依次发生：

• 你将获得此座金矿当天产出的金币；
• 潜伏在此座金矿中的哥布林露出了爪牙，向你索要与它贪婪值相等的金币，如果你没有这么多金币，那你只能将自己所有的金币都交给它，随后它看你穷得可怜，会放你离开。

受到神秘力量的影响，每天早晨都会发生以下某一事件：

• 第 $x$ 座金矿一天产出的金币数量变为 $y$，修改是持久的；
• 第 $x$ 座金矿中潜伏的哥布林的贪婪值变为 $y$，修改是持久的；
• 时光钟楼显灵了！夜世界的状态被回溯到了第 $x$ 天！这意味着 $a,b$ 数组的状态将回退至与第 $x$ 天夜晚一致，初始给出的 $a,b$ 数组表示第 $0$ 天夜晚的状态；
• 有 $k$ 座金矿中潜伏的哥布林变得穷凶极恶，当天夜晚，它们将不再向你索要与它们贪婪值相等的金币，若你目前拥有 $sum$ 枚金币，它们将向你索要 ⌈sum2⌉⌈2sum⌉ 枚金币，随后它们的神智清醒，不再穷凶极恶，但是你仍然很害怕，并希望知道当天夜晚你总共会交给哥布林多少金币，你需要打印这个值。

第一行包含一个整数 $T$，表示测试数据的组数，$1\le T\le 10$。

对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$，分别表示金矿的数量和你需要在夜世界停留的天数；

第二行包含 $n$ 个整数 a1,a2,a3,…,an(0≤ai≤1e9)a1,a2,a3,…,an(0≤ai≤1e9)，表示每座金矿一天产出的金币数量；

第三行包含 $n$ 个整数 b1,b2,b3,…,bn(0≤bi≤1e9)b1,b2,b3,…,bn(0≤bi≤1e9)，表示每座金矿中潜伏的哥布林的贪婪值；

接下来 $m$ 行，第 $i$ 行按如下格式给出一个操作：

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

数据保证：$\sum n\le 2e5$，$\sum m\le 2e5$，$\sum k\le 2e5$。