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} < 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$ .

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$ .

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]$ .