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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
FILE *in, *out;
const int md = 1000000007;
inline int add(int a, int b) {
  a += b;
  if (a >= md) a -= md;
  return a;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += md;
  return a;
}
inline void addf(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
inline void subf(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}
inline int mul(int a, int b) { return (int)((long long)a * b % md); }
inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
inline int inv(int a) { return power(a, md - 2); }
int Linf = 1000000005;
int N, M, K;
pair<int, int> initx[200100];
int pos[200100];
struct node {
  int total;
  long long simplell;
  int simple;
  int L_inc;
  int R_inc;
  int L_sum;
  int R_sum;
  node() {
    total = 0;
    simple = 0;
    simplell = 0;
    L_inc = 0;
    R_inc = 0;
    L_sum = 0;
    R_sum = 0;
  }
  node(int posx, int val) {
    total = 1;
    simplell = val;
    simple = val;
    L_inc = val;
    R_inc = val;
    L_sum = mul((Linf - posx), val);
    R_sum = mul((posx), val);
  }
};
node comb(node a, node b) {
  node res;
  res.total = a.total + b.total;
  res.simplell = a.simplell + b.simplell;
  res.simple = (a.simple + b.simple) % 1000000007;
  res.L_inc = (a.L_inc + add(b.L_inc, mul(b.simple, a.total))) % 1000000007;
  res.R_inc = (b.R_inc + add(a.R_inc, mul(a.simple, b.total))) % 1000000007;
  res.L_sum = (a.L_sum + b.L_sum) % 1000000007;
  res.R_sum = (a.R_sum + b.R_sum) % 1000000007;
  return res;
}
template <class T, int SZ>
struct Seg {
  T seg[2 * SZ], MN = T();
  Seg() {
    for (int i = 0; i < 2 * SZ; i++) seg[i] = T();
  }
  void upd(int p, T value) {
    p += SZ;
    seg[p] = value;
    for (; p > 1; p >>= 1) seg[p >> 1] = comb(seg[(p | 1) ^ 1], seg[p | 1]);
  }
  void build() {
    for (int i = (SZ)-1; i >= 0; i--) seg[i] = comb(seg[2 * i], seg[2 * i + 1]);
  }
  T query(int l, int r) {
    T res1 = MN, res2 = MN;
    r++;
    for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res1 = comb(res1, seg[l++]);
      if (r & 1) res2 = comb(seg[--r], res2);
    }
    return comb(res1, res2);
  }
  long long query2(int l, int r) {
    long long res1 = 0, res2 = 0;
    r++;
    for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res1 += seg[l++].simplell;
      if (r & 1) res2 += seg[--r].simplell;
    }
    return res1 + res2;
  }
};
Seg<node, 200100> S;
int DEBUG(node p) {
  printf("total:%d L_sum:%d R_sum:%d L_inc:%d R_inc:%d\n", p.total, p.L_sum,
         p.R_sum, p.L_inc, p.R_inc);
  return 0;
}
int id[200100];
int solve(int l, int r) {
  int i, j, k;
  int minx, maxx, midx;
  l = id[l - 1];
  r = id[r - 1];
  int indl = lower_bound(pos, pos + M, l) - pos;
  int indr = lower_bound(pos, pos + M, r) - pos;
  int indm;
  int x1, x2, n1, n2;
  int res;
  if (indl < indr) {
    minx = indl;
    maxx = indr - 1;
    node temp, temp2;
    long long sum = S.query2(indl, indr);
    long long templl;
    int bestx = -1;
    while (minx <= maxx) {
      midx = (minx + maxx) / 2;
      templl = S.query2(indl, midx);
      if (templl * 2 <= sum) {
        bestx = max(bestx, midx);
        minx = midx + 1;
      } else
        maxx = midx - 1;
    }
    if (bestx == -1) bestx = indl - 1;
    indm = bestx + 1;
    x1 = pos[bestx + 1] - (indm - indl);
    x2 = pos[bestx + 1];
    n1 = (indm - indl);
    n2 = (indr - indl + 1) - (indm - indl);
    res = 0;
    if (n1 > 0) {
      temp = S.query(indl, indl + n1 - 1);
      k = sub(add(sub(temp.L_sum, mul(temp.simple, (Linf - x1))), temp.L_inc),
              temp.simple);
      addf(res, k);
    }
    if (n2 > 0) {
      temp = S.query(indl + n1, indr);
      k = sub(add(sub(temp.R_sum, mul(temp.simple, (x2 + n2 - 1))), temp.R_inc),
              temp.simple);
      addf(res, k);
    }
    cout << res << "\n";
  } else {
    cout << "0\n";
  }
  return 0;
}
int read() {
  int i, j, k;
  int x, y;
  cin >> N >> K;
  for (i = 0; i < N; i++) {
    cin >> initx[i].first;
    pos[i] = initx[i].first;
    id[i] = initx[i].first;
  }
  for (i = 0; i < N; i++) {
    cin >> initx[i].second;
  }
  sort(pos, pos + N);
  M = unique(pos, pos + N) - pos;
  int ind;
  for (i = 0; i < N; i++) {
    ind = lower_bound(pos, pos + M, initx[i].first) - pos;
    S.upd(ind, node(initx[i].first, initx[i].second));
  }
  for (i = 0; i < K; i++) {
    cin >> x >> y;
    if (x > 0) {
      solve(x, y);
    } else {
      x = -x;
      ind = lower_bound(pos, pos + M, id[x - 1]) - pos;
      S.upd(ind, node(id[x - 1], y));
    }
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  in = stdin;
  out = stdout;
  read();
  return 0;
}