题目背景

• 这里是幻想乡中最多人类居住的地方。因为有许多妖怪也会光临的店，所以会有各种妖怪到访，不过都是些安份的妖怪，这是一个和平的地方（×1稗田家所在地，毫无疑问也在人类村落。

• 人类必要的生活用品，都能在这里买到。也有一些专门退治妖怪的人住在这，所以这里的生活是较安全的。

• 要说人类村落为什么没有被袭击，那就是妖怪的贤者在背后保护（×2幻想乡的人类灭绝的话，妖怪们也不好过。）。不外出的话，就不会遇上大难。

• 若外出途中遇到比自己强的妖怪（×3高概率的对方比自己强。），就恭恭敬敬地打招呼吧。 还有令人意外的是，有很多店会开到深夜，夜晚会变成妖怪专用店。妖怪多在夜晚活动，店也在那段时间兴旺。可以说妖怪才是很好的客人。

• 特别是卖酒的店，妖怪和人类同乐已成了日常一景。

$$\tag*{——摘自《东方求闻史纪》}$$

题目描述

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

人间之里可以抽象为一条坐标轴，其上有 $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$ 的房屋。

输入格式

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

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

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

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

输出格式

对于每个 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

提示

【样例解释】

对于第一个询问，共有两座房屋受到影响，一处位于 $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$