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