Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

F. Putting Boxes Together
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Example
Input
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
Output
0
10
3
4
18
7
Note

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