「Wdsr-1」人间之里

- 这里是幻想乡中最多人类居住的地方。因为有许多妖怪也会光临的店，所以会有各种妖怪到访，不过都是些安份的妖怪，这是一个和平的地方（×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$ | $100$ | $10$ $2$ | $8 \times 10 ^ 3$ | $8 \times 10 ^ 3$ | $15$ $3$ | $8 \times 10 ^ 3$ | $10 ^ 9$ | $5$ $4$ | $10 ^ 5$ | $10 ^ 5$ | $30$ $5$ | $10 ^ 5$ | $10 ^ 9$ | $10$ $6$ | $3 \times 10 ^ 5$ | $10 ^ 9$ | $30$