Problem: 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 ⋅ 10^9 + 13 and 2 ⋅ 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 ≤ n, q ≤ 2 ⋅ 10^5) — the number of boxes and the number of queries.

The second line contains n integers a_1, a_2, ... a_n (1 ≤ a_i ≤ 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, ... w_n (1 ≤ w_i ≤ 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 ≤ id ≤ n, 1 ≤ nw ≤ 10^9). If x > 0, then the query is of the second type, where l = x and r = y (1 ≤ l_j ≤ r_j ≤ 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 ⋅ |1 - 4| + 1 ⋅ |2 - 5| + 1 ⋅ |6 - 6| + 1 ⋅ |7 - 7| + 2 ⋅ |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]. 

Solution (in JAVA):

Solution:
import java.lang.*;
import java.math.*;
import java.util.*;
import java.io.*;

public class Main {
    void solve(){
        int n=ni(),q=ni();
        a=new long[n+1];
        w=new long[n+1];
        for(int i=1;i<=n;i++) a[i]=nl()-i;
        for(int i=1;i<=n;i++) w[i]=nl();
        BIT1=new long[n+1];
        BIT2=new long[n+1];

        for(int i=1;i<=n;i++){
            update1(n,i,w[i]);
            update2(n,i,mul(a[i],w[i]));
        }

        while(q-->0){
            int x=ni(),y=ni();
            //System.out.println(x+" "+y);
            if(x<0){
                update1(n,-x,y-w[-x]);
                update2(n,-x,mul(a[-x],sub(y,w[-x])));
                w[-x]=y;
            }else {
                long slr=querry1(x,y);
                int l=x,r=y,k=-1;
                while(l<=r){
                    int mid=(l+r)/2;
                   // System.out.println(l+" "+r+" "+mid);
                    long s1=querry1(x,mid-1),s2=querry1(x,mid);
                    if(2*s1<=slr && 2*s2>=slr){
                        k=mid;
                    }
                    if(2*s2<slr) l=mid+1;
                    else r=mid-1;
                }
                long L=mul(a[k],querry1(x,k-1));
                L=sub(L,querry2(x,k-1));
                long R=querry2(k+1,y);
                R=sub(R,mul(a[k],querry1(k+1,y)));
                long ans=add(L,R);
                pw.println(ans);
            }
        }

    }
    long BIT1[];
    long BIT2[];


    long a[];
    long w[];
    void update1(int n,int x,long val){
        for(;x<=n;x+=(x&-x)) BIT1[x]+=val;
    }
    long querry1(int l,int r){
        if(l>r) return 0;
        long ans=querry1(r);
        ans-=querry1(l-1);
        return ans;
    }
    long querry1(int x){
        long ans=0;
        for(;x>0;x-=(x&-x)) ans+=BIT1[x];
        return ans;
    }

    void update2(int n,int x,long val){
        for(;x<=n;x+=(x&-x)) BIT2[x]=add(BIT2[x],val);
    }
    long querry2(int l,int r){
        if(l>r) return 0;
        long ans=querry2(r);
        ans=sub(ans,querry2(l-1));
        return ans;
    }
    long querry2(int x){
        long ans=0;
        for(;x>0;x-=(x&-x)) ans=add(ans,BIT2[x]);
        return ans;
    }





    long add(long a,long b){
        if(a>=M) a%=M;
        if(b>=M) b%=M;

        a+=b;
        if(a>=M) a-=M;
        return a;
    }
    long sub(long a,long b){
        if(a>=M) a%=M;
        if(b>=M) b%=M;

        a-=b;
        if(a<0) a+=M;
        return a;
    }
    long mul(long a,long b){
        if(a>=M) a%=M;
        if(b>=M) b%=M;

        a*=b;
        if(a>=M )a%=M;
        return a;
    }



    long M= (long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";
    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    public static void main(String[] args) throws Exception { new Main().run(); }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }

}