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

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

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

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

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

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

Input

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

对于每组测试数据：

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

• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，$(0 \le a_i \le 10^9)$，表示每座金矿一天产出的金币数量；

• 第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$，$(0 \le b_i \le 10^9)$，表示每座金矿中潜伏的哥布林的贪婪值；

• 接下来 $m$ 行，每行表示一个操作，格式如下：

  • 1 x y ：第 $x$ 座金矿一天产出的金币数量变为 $y$；
  • 2 x y ：第 $x$ 座金矿中潜伏的哥布林的贪婪值变为 $y$；
  • 3 x ：夜世界的状态被回溯到了第 $x$ 天（$0 \le x < i$）；
  • 4 k pos_1 pos_2 ... pos_k ：潜伏在这些金矿中的哥布林变得穷凶极恶，需要输出当天夜晚你总共会交给哥布林多少金币。

数据保证：$\sum n \le 2 \times 10^5$，$\sum m \le 2 \times 10^5$，$\sum k \le 2 \times 10^5$。

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

Output

18