Description

有一位新的 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$ 个音响的音量全部设置为相同的值，使得消耗的能量最小。如果有多种方式可以达到最小能量，他会选择最终音量最小的那一种。

作为旁观者，你想知道对于每个类型 2 的事件，Darko 最终将音响设置成了多少音量。

Input Format

第一行包含两个整数 $N$ 和 $Q$，表示音响的数量和事件的数量。
第二行包含 $N$ 个整数 $A_i$，表示每个音响当前的音量。
第三行包含 $N$ 个整数 $B_i$，表示每个音响每调整 1 单位音量所需的能量。
接下来的 $Q$ 行，每行描述一个事件，格式如上所述。所有输入均为整数。

Output Format

对于每个类型 2 的事件，输出 Darko 最终将音响设置成的音量。

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
0
-7
9

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

-3
-7

Hint

输入范围

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

由 ChatGPT 4.1 翻译