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

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Putting Boxes Together

time limit per test

2.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:33:12 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|