Description

虽然人间之里可以说是全幻想乡对于人类最安全的地方，但是异变发生时，还是可能会出现意外，所以要建立避难所。

人间之里可以抽象为一条坐标轴，其上有 $n$ 个点上建有房屋。这些房屋的坐标分别为 $x_1,x_2,...,x_n$，且在第 $i$ 座房屋中居住着 $v_i$ 位居民。

每次发生异变时，会有一段坐标连续的房屋受到影响，而此时便需要在某一坐标处建立避难所。一个避难所的"不便程度"为受影响的房屋中的每一个居民与避难所的距离之和。

（举例来说，假设只有房屋 $i$ 受到了影响，则在 $z$ 处建立避难所的"不便程度"为 $v_i*|x_i-z|$ ）

当然，坐落在幻想乡中人间之里的不可能一成不变，所以房屋的位置和居民的数量都可能会发生变化。

具体来说，你需要处理 $m$ 次询问或修改，每一次输入的格式如下：

• 1 l r，表示询问 当坐标位于 $[l,r]$ 范围内的房屋受到异变影响时，在所有建立避难所的方案中，最小的"不便程度"是多少。

• 2 a b c，表示将第 $a$ 座房屋的坐标修改为 $b$，其中居住的村民的数量变为 $c$ 。

注意：

• 在 $1$ 操作中的"受到异变影响"均为假设，所以对之后的查询不产生作用。

• 在 $2$ 操作中发生变化的是第 $a$ 座房屋而不是坐标为 $a$ 的房屋。

Input Format

第一行两个整数，$n,m$。

第二行 $n$ 个整数，$x_i$。

第三行 $n$ 个整数，$v_i$。

接下来 $m$ 行，每行描述一个操作。

Output Format

对于每个 1 l r 操作，输出建立避难所的最小"不便程度"。

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

9
82
9
0
0

Hint

【样例解释】

对于第一个询问，共有两座房屋受到影响，一处位于 $x=4$ 处，有 $3$ 位村民，一处位于 $x=7$ 处，有 $6$ 位村民。

避难所选在 $x=7$ 处时，"不便程度"为：

$$\left\vert 7 - 4 \right\vert \times 3 + \left\vert 7 - 7 \right\vert \times 6 = 9$$

可以证明 $9$ 是所有建立避难所的方案中"不便程度"的最小值。

---

【数据范围】

• 对于 $100\%$ 的数据：

  $1 \le n,m \le 3 \times 10 ^ 5$。

  $1 \le a \le n$，$-10 ^ 9 \le l \le r \le 10 ^ 9 \le n$，$-10 ^ 9 \le x_i,b \le 10 ^ 9$，$0 \le v_i,c \le 10 ^ 3$。

• 详细的数据范围：

  设 $mx$ 为所有输入的整数绝对值的最大值。

  测试点编号	$n,m \le$	$mx \le$	分值
  $1$	$100$		$10$
  $2$	$8 \times 10 ^ 3$	$8 \times 10 ^ 3$	$15$
  $3$		$10 ^ 9$	$5$
  $4$	$10 ^ 5$	$10 ^ 5$	$30$
  $5$		$10 ^ 9$	$10$
  $6$	$3 \times 10 ^ 5$		$30$