Putting Boxes Together
Description
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} < 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:
- $id$ $nw$ — weight $w_{id}$ of the box $id$ becomes $nw$.
- $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$.
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} < 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 < 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 > 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$.
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$.
Input
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} < 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 < 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 > 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$.
Output
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$.
Samples
5 8
1 2 6 7 10
1 1 1 1 2
1 1
1 5
1 3
3 5
-3 5
-1 10
1 4
2 5
0
10
3
4
18
7
Note
Let's go through queries of the example:
- $1\ 1$ — there is only one box so we don't need to move anything.
- $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$.
- $1\ 3$ — we can move boxes to segment $[1, 3]$.
- $3\ 5$ — we can move boxes to segment $[7, 9]$.
- $-3\ 5$ — $w_3$ is changed from $1$ to $5$.
- $-1\ 10$ — $w_1$ is changed from $1$ to $10$. The weights are now equal to $w = [10, 1, 5, 1, 2]$.
- $1\ 4$ — we can move boxes to segment $[1, 4]$.
- $2\ 5$ — we can move boxes to segment $[5, 8]$.