CF1030F.Putting Boxes Together

There is an infinite line consisting of cells. There are $n$ boxes in some cells of this line. The $i$-th box stands in the cell $a_i$ and has weight $w_i$. All $a_i$ are distinct, moreover, $a_{i - 1} \lt a_i$ holds for all valid $i$.

You would like to put together some boxes. Putting together boxes with indices in the segment $[l, r]$ means that you will move some of them in such a way that their positions will form some segment $[x, x + (r - l)]$.

In one step you can move any box to a neighboring cell if it isn't occupied by another box (i.e. you can choose $i$ and change $a_i$ by $1$, all positions should remain distinct). You spend $w_i$ units of energy moving the box $i$ by one cell. You can move any box any number of times, in arbitrary order.

Sometimes weights of some boxes change, so you have queries of two types:

1. $id$ $nw$ — weight $w_{id}$ of the box $id$ becomes $nw$.
2. $l$ $r$ — you should compute the minimum total energy needed to put together boxes with indices in $[l, r]$. Since the answer can be rather big, print the remainder it gives when divided by $1000\,000\,007 = 10^9 + 7$. Note that the boxes are not moved during the query, you only should compute the answer.

Note that you should minimize the answer, not its remainder modulo $10^9 + 7$. So if you have two possible answers $2 \cdot 10^9 + 13$ and $2 \cdot 10^9 + 14$, you should choose the first one and print $10^9 + 6$, even though the remainder of the second answer is $0$.

存在一条由无数个格子组成的无限长直线。这条直线上有 $n$ 个箱子，位于某些格子中。第 $i$ 个箱子位于格子 $a_i$，重量为 $w_i$。所有 $a_i$ 互不相同，且对所有合法的 $i$，均满足 $a_{i - 1} \lt a_i$。

你希望将若干个箱子聚拢在一起。“将下标在区间 $[l, r]$ 内的所有箱子聚拢”意味着：你需要移动其中一些箱子，使得它们最终所处的位置构成某个连续区间 $[x, x + (r - l)]$（即共 $r-l+1$ 个连续整数位置）。

每一步操作中，你可以将任意一个箱子向相邻格子移动一格，前提是目标格子未被其他箱子占据（即你可以选择某个 $i$，将 $a_i$ 增加或减少 $1$，且所有位置必须始终保持互不相同）。将第 $i$ 个箱子移动一格需消耗 $w_i$ 单位能量。你可以对任意箱子进行任意次数的移动，且移动顺序任意。

有时某些箱子的重量会发生变化，因此你将收到两类查询：

1. id nw —— 将第 id 个箱子的重量 $w_{id}$ 更新为 $nw$；
2. l r —— 计算将下标在区间 $[l, r]$ 内的所有箱子聚拢所需的最小总能量。由于答案可能非常大，请输出其对 $1000\,000\,007 = 10^9 + 7$ 取模的结果。注意：查询过程中箱子并不实际移动，你只需计算答案。

注意：你需要最小化的是答案本身，而非其对 $10^9 + 7$ 取模后的值。因此，若两个可能的答案分别为 $2 \cdot 10^9 + 13$ 和 $2 \cdot 10^9 + 14$，则应选择前者，并输出 $(2 \cdot 10^9 + 13) \bmod (10^9 + 7) = 10^9 + 6$，即使后者的模值为 $0$。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of boxes and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \le a_i \le 10^9$) — the positions of the boxes. All $a_i$ are distinct, $a_{i - 1} \lt a_i$ holds for all valid $i$.

The third line contains $n$ integers $w_1, w_2, \dots w_n$ ($1 \le w_i \le 10^9$) — the initial weights of the boxes.

Next $q$ lines describe queries, one query per line.

Each query is described in a single line, containing two integers $x$ and $y$. If $x \lt 0$, then this query is of the first type, where $id = -x$, $nw = y$ ($1 \le id \le n$, $1 \le nw \le 10^9$). If $x \gt 0$, then the query is of the second type, where $l = x$ and $r = y$ ($1 \le l_j \le r_j \le n$). $x$ can not be equal to $0$.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别表示箱子的数量和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示各个箱子的位置。所有 $a_i$ 互不相同，且对所有合法的 $i$ 均满足 $a_{i - 1} \lt a_i$。

第三行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$）—— 表示各个箱子的初始重量。

接下来 $q$ 行描述查询，每行一个查询。

每个查询由一行描述，包含两个整数 $x$ 和 $y$。若 $x \lt 0$，则该查询为第一类查询，其中 $id = -x$，$nw = y$（$1 \le id \le n$，$1 \le nw \le 10^9$）。若 $x \gt 0$，则该查询为第二类查询，其中 $l = x$，$r = y$（$1 \le l_j \le r_j \le n$）。$x$ 不可能等于 $0$。

For each query of the second type print the answer on a separate line. Since answer can be large, print the remainder it gives when divided by $1000\,000\,007 = 10^9 + 7$.

对于每个第二类查询，在单独一行输出答案。由于答案可能很大，请输出其对 $1000\,000\,007 = 10^9 + 7$ 取模的结果。

Let's go through queries of the example:

1. $1\ 1$ — there is only one box so we don't need to move anything.
2. $1\ 5$ — we can move boxes to segment $[4, 8]$: $1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10$.
3. $1\ 3$ — we can move boxes to segment $[1, 3]$.
4. $3\ 5$ — we can move boxes to segment $[7, 9]$.
5. $-3\ 5$ — $w_3$ is changed from $1$ to $5$.
6. $-1\ 10$ — $w_1$ is changed from $1$ to $10$. The weights are now equal to $w = [10, 1, 5, 1, 2]$.
7. $1\ 4$ — we can move boxes to segment $[1, 4]$.
8. $2\ 5$ — we can move boxes to segment $[5, 8]$.

我们来逐步分析示例中的各个查询：

1. $1\ 1$ — 只有一个箱子，因此无需移动任何东西。
2. $1\ 5$ — 我们可将箱子移至区间 $[4, 8]$：$1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10$。
3. $1\ 3$ — 我们可将箱子移至区间 $[1, 3]$。
4. $3\ 5$ — 我们可将箱子移至区间 $[7, 9]$。
5. $-3\ 5$ — $w_3$ 的值由 $1$ 改为 $5$。
6. $-1\ 10$ — $w_1$ 的值由 $1$ 改为 $10$。此时权重数组变为 $w = [10, 1, 5, 1, 2]$。
7. $1\ 4$ — 我们可将箱子移至区间 $[1, 4]$。
8. $2\ 5$ — 我们可将箱子移至区间 $[5, 8]$。