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 𝑎𝑖ai and has weight 𝑤𝑖wi. All 𝑎𝑖ai are distinct, moreover, 𝑎𝑖−1<𝑎𝑖ai−1<ai 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 𝑎𝑖ai by 11, all positions should remain distinct). You spend 𝑤𝑖wi 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 𝑤𝑖𝑑wid 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 1000000007=109+71000000007=109+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 109+7109+7. So if you have two possible answers 2⋅109+132⋅109+13 and 2⋅109+142⋅109+14, you should choose the first one and print 109+6109+6, even though the remainder of the second answer is 00.

Input

The first line contains two integers 𝑛n and 𝑞q (1≤𝑛,𝑞≤2⋅1051≤n,q≤2⋅105) — the number of boxes and the number of queries.

The second line contains 𝑛n integers 𝑎1,𝑎2,…𝑎𝑛a1,a2,…an (1≤𝑎𝑖≤1091≤ai≤109) — the positions of the boxes. All 𝑎𝑖ai are distinct, 𝑎𝑖−1<𝑎𝑖ai−1<ai holds for all valid 𝑖i.

The third line contains 𝑛n integers 𝑤1,𝑤2,…𝑤𝑛w1,w2,…wn (1≤𝑤𝑖≤1091≤wi≤109) — 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 𝑥<0x<0, then this query is of the first type, where 𝑖𝑑=−𝑥id=−x, 𝑛𝑤=𝑦nw=y (1≤𝑖𝑑≤𝑛1≤id≤n, 1≤𝑛𝑤≤1091≤nw≤109). If 𝑥>0x>0, then the query is of the second type, where 𝑙=𝑥l=x and 𝑟=𝑦r=y (1≤𝑙𝑗≤𝑟𝑗≤𝑛1≤lj≤rj≤n). 𝑥x can not be equal to 00.

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 1000000007=109+71000000007=109+7.

Note

Let's go through queries of the example:

1. 1 11 1 — there is only one box so we don't need to move anything.
2. 1 51 5 — we can move boxes to segment [4,8][4,8]: 1⋅|1−4|+1⋅|2−5|+1⋅|6−6|+1⋅|7−7|+2⋅|10−8|=101⋅|1−4|+1⋅|2−5|+1⋅|6−6|+1⋅|7−7|+2⋅|10−8|=10.
3. 1 31 3 — we can move boxes to segment [1,3][1,3].
4. 3 53 5 — we can move boxes to segment [7,9][7,9].
5. −3 5−3 5 — 𝑤3w3 is changed from 11 to 55.
6. −1 10−1 10 — 𝑤1w1 is changed from 11 to 1010. The weights are now equal to 𝑤=[10,1,5,1,2]w=[10,1,5,1,2].
7. 1 41 4 — we can move boxes to segment [1,4][1,4].
8. 2 52 5 — we can move boxes to segment [5,8][5,8].