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