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;
const long long mod = 1e9 + 7;
int n, q, a[300001];
const int MAX = 1 << 18;
struct sum_seg {
  long long tr[MAX << 1];
  void upd(int cur, long long val) {
    tr[cur += MAX] = val;
    cur >>= 1;
    while (cur) {
      tr[cur] = tr[cur << 1] + tr[cur << 1 | 1];
      cur >>= 1;
    }
  }
  long long sum(int l, int r) {
    long long res = 0;
    l += MAX;
    r += MAX;
    while (l <= r) {
      if (l & 1) res += tr[l++];
      if (!(r & 1)) res += tr[r--];
      l >>= 1;
      r >>= 1;
    }
    return res;
  }
} sum;
struct td {
  long long lsum, rsum, lwsum, rwsum;
  td() {}
  td(long long a, long long b, long long c, long long d)
      : lsum(a), rsum(b), lwsum(c), rwsum(d) {}
};
struct wsum_seg {
  long long ltr[MAX << 1], rtr[MAX << 1];
  pair<long long, long long> upd(int cur, int s, int f, int idx) {
    if (f < idx || s > idx)
      return pair<long long, long long>(ltr[cur], rtr[cur]);
    else if (s == f)
      return pair<long long, long long>(0, 0);
    else {
      int nx = cur << 1, md = (s + f) >> 1, l = f - md;
      pair<long long, long long> lv = upd(nx, s, md, idx),
                                 rv = upd(nx + 1, md + 1, f, idx);
      ltr[cur] = ((lv.first + rv.first) % mod +
                  sum.tr[nx] % mod * (a[f] - l - a[md]) % mod) %
                 mod;
      rtr[cur] = ((lv.second + rv.second) % mod +
                  sum.tr[nx + 1] % mod * (a[md + 1] - (a[s] + l)) % mod) %
                 mod;
      return pair<long long, long long>(ltr[cur], rtr[cur]);
    }
  }
  td find(int cur, int s, int f, int l, int r) {
    if (f < l || s > r)
      return td(0, 0, 0, 0);
    else if (l <= s && f <= r)
      return td(sum.tr[cur] % mod, sum.tr[cur] % mod, ltr[cur], rtr[cur]);
    else {
      int nx = cur << 1, md = (s + f) >> 1, len = min(r, f) - md;
      if (r <= md)
        return find(nx, s, md, l, r);
      else if (l >= md + 1)
        return find(nx + 1, md + 1, f, l, r);
      td lv = find(nx, s, md, l, r), rv = find(nx + 1, md + 1, f, l, r);
      td res;
      res.lwsum = ((lv.lwsum + rv.lwsum) % mod +
                   lv.lsum % mod * (a[min(r, f)] - len - a[md]) % mod) %
                  mod;
      len = md - max(l, s) + 1;
      res.rwsum = ((lv.rwsum + rv.rwsum) % mod +
                   rv.rsum % mod * (a[md + 1] - (a[max(l, s)] + len)) % mod) %
                  mod;
      res.lsum = (lv.lsum + rv.lsum) % mod;
      res.rsum = (lv.rsum + rv.rsum) % mod;
      return res;
    }
  }
} wsum;
int get_point(int s, int l, int r) {
  int lo = l - 1, up = r + 1;
  while (up - lo > 1) {
    int md = (lo + up) >> 1;
    if (a[md] <= s + (md - l))
      lo = md;
    else
      up = md;
  }
  return lo;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = n + 1; i < MAX; i++) a[i] = a[i - 1] + 1;
  for (int i = 1; i <= n; i++) {
    long long val;
    scanf("%lld", &val);
    sum.upd(i, val);
    wsum.upd(1, 0, MAX - 1, i);
  }
  int x, y;
  while (q--) {
    scanf("%d%d", &x, &y);
    if (x < 0) {
      x = -x;
      sum.upd(x, y);
      wsum.upd(1, 0, MAX - 1, x);
    } else {
      int lo = a[x - 1], up = a[y + 1];
      while (up - lo > 1) {
        int md = (lo + up) >> 1;
        int j = get_point(md, x, y);
        if (sum.sum(x, j) <= sum.sum(j + 1, y))
          lo = md;
        else
          up = md;
      }
      int i = up, j = get_point(up, x, y);
      long long ans = 0;
      if (j >= x) {
        td val = wsum.find(1, 0, MAX - 1, x, j);
        ans = (ans + val.lwsum % mod +
               val.lsum % mod * (i + j - x - a[j]) % mod) %
              mod;
      }
      if (j + 1 <= y) {
        td val = wsum.find(1, 0, MAX - 1, j + 1, y);
        ans = (ans + val.rwsum % mod +
               val.rsum % mod * (a[j + 1] - (i + j - x + 1)) % mod) %
              mod;
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}