有一位新 DJ 来到了镇上。DJ Darko 需要调试他的音箱。他有一排 $N$ 个音箱，第 $i$ 个音箱的初始音量设为 $A_i$。调节音量比较困难，因此第 $i$ 个音箱每增加或减少 1 个单位的音量，都需要消耗 $B_i$ 的能量。

不幸的是，Darko 的邪恶双胞胎兄弟 Karko 喜欢捉弄他。接下来会发生 $Q$ 个事件：

1 l r x
2 l r

对于类型 1 的事件，Karko 将第 $l$ 个到第 $r$ 个音箱的音量全部改变 $x$。对于类型 2 的事件，Darko 将第 $l$ 个到第 $r$ 个音箱的音量全部设为同一个值，要求消耗的能量最少。如果存在多种方案，他会选择其中最终音量最小的那一种。

作为旁观者，你需要求出 Darko 在每次类型 2 事件中将音箱设定的音量。

输入格式

第一行包含音箱数量 $N$ 和事件数量 $Q$。第二行包含 $N$ 个数字 $A_i$，表示音箱的当前音量。第三行包含 $N$ 个数字 $B_i$，表示将第 $i$ 个音箱音量改变 1 所需的能量。接下来的 $Q$ 行描述了 $Q$ 个事件，格式如上所述。输入中的所有数字均为整数。

数据范围

• $1 \le N, Q \le 200\,000$
• $0 \le A_i, B_i \le 10^9$
• $1 \le l \le r \le N$
• $-10^9 \le x \le 10^9$

输出格式

对于每个类型 2 的事件，输出 Darko 将音箱设定的音量。

样例

输入 1

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

输出 1

1
0
-7
9

输入 2

8 3
4 3 9 3 7 6 4 8
9 5 8 5 2 2 1 8
1 1 7 -10
2 5 5
2 4 7

输出 2

-3
-7