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;
struct Box {
  long long w, x;
};
struct Fenwick {
  vector<long long> V;
  Fenwick(int N) : V(N + 10) {}
  void add(int x, long long v) {
    for (int i = x + 1; i < V.size(); i += (i & -i)) {
      V[i] += v;
    }
  }
  long long get(int x) {
    long long r = 0;
    for (int i = x + 1; i > 0; i -= (i & -i)) {
      r += V[i];
    }
    return r;
  }
  long long segSum(int i, int j) { return get(j) - get(i - 1); }
};
template <class T, class U>
struct SegmentTree {
  struct Node {
    bool hasCarry = 0;
    int b = 0, e = 0;
    U carry = U();
    T val = T();
    Node() {}
    void join(const Node &l, const Node &r) {
      val = l.val + r.val;
      b = l.b;
      e = r.e;
    }
    void update(const U &u) {
      carry += u;
      u(val);
      hasCarry = 1;
    }
    void pushDown(Node &l, Node &r) {
      if (!hasCarry) return;
      l.update(carry.trim(0, r.e - r.b + 1));
      r.update(carry.trim(l.e - l.b + 1, 0));
      carry = U();
      hasCarry = 0;
    }
  };
  vector<Node> V;
  int N;
  SegmentTree(int N) : V(2 * N), N(N) {}
  template <class I>
  void create(const vector<I> &VEC, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (b == e) {
      V[n].val = T(VEC[b]), V[n].b = b, V[n].e = e;
    } else {
      int m = (b + e) / 2;
      create(VEC, b, m);
      create(VEC, m + 1, e);
      V[n].join(V[(((b) + (m)) | ((b) != (m)))],
                V[(((m + 1) + (e)) | ((m + 1) != (e)))]);
    }
  }
  T query(int i, int j, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (i <= b && e <= j) {
      return V[n].val;
    } else {
      int m = (b + e) / 2;
      V[n].pushDown(V[(((b) + (m)) | ((b) != (m)))],
                    V[(((m + 1) + (e)) | ((m + 1) != (e)))]);
      if (i > m) return query(i, j, m + 1, e);
      if (j <= m) return query(i, j, b, m);
      return query(i, j, b, m) + query(i, j, m + 1, e);
    }
  }
  int findOkPrefix(int i, const function<bool(T)> &isOk) {
    static int stk[50];
    int ssz = 0;
    stk[ssz++] = ((((0) + (N - 1)) | ((0) != (N - 1))));
    T acum;
    int sz = 0;
    while (ssz > 0) {
      int t = stk[--ssz];
      Node &n = V[t];
      int m = (n.b + n.e) / 2;
      if (n.e < i) continue;
      T newAcum = sz == 0 ? n.val : (acum + n.val);
      if (i <= n.b) {
        if (isOk(newAcum)) {
          sz += n.e - n.b + 1;
          acum = newAcum;
        } else {
          if (n.b == n.e) return sz;
          stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
          stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
        }
      } else {
        if (n.b == n.e) continue;
        stk[ssz++] = ((((m + 1) + (n.e)) | ((m + 1) != (n.e))));
        stk[ssz++] = ((((n.b) + (m)) | ((n.b) != (m))));
      }
    }
    return sz;
  }
  void update(int i, int j, const U &v, int b = 0, int e = -1) {
    if (e == -1) e = N - 1;
    int n = (((b) + (e)) | ((b) != (e)));
    if (i <= b && e <= j) {
      V[n].update(v.trim(max(b - i, 0), max(j - e, 0)));
    } else if (i > e || j < b)
      return;
    else {
      int m = (b + e) / 2;
      int l = (((b) + (m)) | ((b) != (m))),
          r = (((m + 1) + (e)) | ((m + 1) != (e)));
      V[n].pushDown(V[l], V[r]);
      update(i, j, v, b, m);
      update(i, j, v, m + 1, e);
      V[n].join(V[l], V[r]);
    }
  }
};
struct Sum {
  long long s;
  Sum(long long w = 0) { s = w; }
  Sum operator+(const Sum &o) const {
    Sum r;
    r.s = (s + o.s);
    return r;
  }
};
struct ToSides {
  int toL, toR, pl, pr, w;
  ToSides(Box b = (Box){0, 0}) {
    toL = 0;
    toR = 0;
    pl = b.x;
    pr = b.x;
    w = b.w;
  }
  ToSides operator+(const ToSides &a) const {
    ToSides r = a;
    r.toL = (toL + a.toL + (1LL * (a.pl - pl) * a.w)) % 1000000007;
    r.toR = (toR + a.toR + (1LL * (a.pr - pr) * w)) % 1000000007;
    r.pl = pl;
    r.pr = a.pr;
    r.w = (a.w + w) % 1000000007;
    return r;
  }
};
struct Replace {
  long long w;
  Replace(long long w = 0) { this->w = w; }
  Replace trim(int l, int r) const { return *this; }
  void operator+=(const Replace &a) { w = a.w; }
  void operator()(ToSides &a) const { a.w = w; }
  void operator()(Sum &a) const { a.s = w; }
};
int main() {
  int N, Q;
  cin >> N >> Q;
  vector<Box> V(N);
  Fenwick FX(N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld", &V[i].x);
    V[i].x -= i;
    FX.add(i, V[i].x);
  }
  Fenwick F(N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld", &V[i].w);
    F.add(i, V[i].w);
  }
  SegmentTree<ToSides, Replace> ST(N);
  SegmentTree<Sum, Replace> SU(N);
  ST.create(V);
  {
    vector<long long> WW(N);
    for (int i = 0; i < N; ++i) {
      WW[i] = V[i].w;
    }
    SU.create(WW);
  }
  for (int i = 0; i < Q; ++i) {
    long long l, r;
    scanf("%lld%lld", &l, &r);
    if (l < 0) {
      long long id = (-l) - 1, nw = r;
      ST.update(id, id, Replace(nw));
      SU.update(id, id, Replace(nw));
    } else {
      l--;
      r--;
      long long tots = SU.query(l, r).s;
      int sz = SU.findOkPrefix(l, [tots](Sum s) { return s.s * 2 < tots; });
      int m = l + sz;
      long long a = ST.query(l, m).toR;
      long long b = ST.query(m, r).toL;
      printf("%d\n", (int)((a + b) % 1000000007));
    }
  }
}