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.io.*;
import java.math.*;
import java.util.*;

public class A {
	public static void main (String[] args) { new A(); }

	long MOD = (long)1e9+7;
	
	A() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");
		
//		BIT tmp = new BIT(10);
//		tmp.update(0, 10);
//		tmp.update(1, 1);
//		tmp.update(2, 14);
//		System.out.println(tmp.getKth(11));

		int n = fs.nextInt(), q = fs.nextInt();
		BIT weight = new BIT(n), offset = new BIT(n);
		int[] pos = new int[n], ws = new int[n];
		int[] offs = new int[n];
		
		for(int i = 0; i < n; i++) pos[i] = fs.nextInt();
		for(int i = 0; i < n; i++) {
			ws[i] = fs.nextInt();
			offs[i] = mult(ws[i], sub(pos[i], i));
			weight.update(i, ws[i]);
			offset.update(i, offs[i]);
		}
		
		for(int qq = 1; qq <= q; qq++) {
			int x = fs.nextInt(), y = fs.nextInt();
			if(x < 0) {
				int id = -x; id--;
				int nw = y;
				
				weight.update(id, -ws[id]);
				offset.update(id, -offs[id]);
				
				ws[id] = nw;
				offs[id] = mult(ws[id], sub(pos[id], id));
				
				weight.update(id, ws[id]);
				offset.update(id, offs[id]);
			}
			else {
				int l = x-1;
				int r = y-1;
				
				long range = weight.range(l, r);
				long tot = range/2+(range&1);
				if(l > 0) tot += weight.range(0, l-1);
				int spot = weight.getKth(tot-1);
				
				long res = 0;
				if(spot > l) {
					int rgt = mult(sub(pos[spot], spot), weight.range(l, spot-1));
					int lft = (int)(offset.range(l, spot-1)%MOD);
					res += sub(rgt, lft);
				}
				if(spot < r) {
					int rgt = mult(sub(pos[spot], spot), weight.range(spot+1, r));
					int lft = (int)(offset.range(spot+1, r)%MOD);
					res += sub(lft, rgt);
				}
				while(res >= MOD) res -= MOD;
				out.println(res);
			}
		}
		
		out.close();
	}
	
	int mult(long a, long b) {
		if(a >= MOD) a %= MOD;
		if(b >= MOD) b %= MOD;
		
		a *= b;
		if(a >= MOD) a %= MOD;
		return (int)a;
	}
	
	int sub(int a, int b) {
		a -= b;
		if(a < 0) a += MOD;
		return a;
	}
	
	class BIT {
		int n;
		long[] tree;
		public BIT(int n) {
			this.n = n;
			tree = new long[n + 2];
		}
		long read(int i) {
			i++;
			long sum = 0;
			while (i > 0) {
				sum += tree[i];
				i -= i & -i;
			}
			return sum;
		}
		long range(int i, int j) {
			long res = read(j);
			if(i > 0) res -= read(i-1);
			return res;
		}
		void update(int i, long val) {
			i++;
			while (i <= n) {
				tree[i] += val;
				i += i & -i;
			}
		}
		int getKth(long k) {
			int e=Integer.highestOneBit(n), o=0;
			for (; e!=0; e>>=1) {
				if (e+o<=n && tree[e+o]<=k) {
					k-=tree[e+o];
					o+=e;
				}
			}
			return o;
		}
	}
	
	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		FastScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}
		String next() {
			if(st.hasMoreTokens()) return st.nextToken();
			try { st = new StringTokenizer(br.readLine()); } catch (Exception e) {}
			return next();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
}