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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename T1, typename T2>
inline void chkmin(T1 &first, T2 second) {
  if (first > second) first = second;
}
template <typename T1, typename T2>
inline void chkmax(T1 &first, T2 second) {
  if (first < second) first = second;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
  _out << _p.first << ' ' << _p.second;
  return _out;
}
template <typename T, typename U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
  _in >> _p.first >> _p.second;
  return _in;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
  if (_v.empty()) {
    return _out;
  }
  _out << _v.front();
  for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
  for (auto &_i : _v) {
    _in >> _i;
  }
  return _in;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const unordered_set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const unordered_multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const unordered_map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
const int N = 1 << 19;
const int p = 1e9 + 7;
struct seg_tree_no_mod {
  long long t[N * 2 + 1];
  void change(int i, long long v) {
    i += N;
    while (i > 0) {
      t[i] += v;
      i >>= 1;
    }
  }
  long long k;
  long long gets(int i, int L, int R, int Ln, int Rn) {
    if (Ln <= L && R <= Rn) {
      return t[i];
    }
    if (Rn <= L || R <= Ln) {
      return 0;
    }
    int M = (L + R) >> 1;
    return gets(i * 2, L, M, Ln, Rn) + gets(i * 2 + 1, M, R, Ln, Rn);
  }
  int get(int i, int L, int R, int Ln, int Rn) {
    if (R <= Ln || Rn <= L) return -1;
    if (Ln <= L && R <= Rn) {
      if (k > t[i]) {
        k -= t[i];
        return -1;
      }
    }
    if (L + 1 == R) {
      return i - N;
    }
    int M = (L + R) >> 1;
    int ans = get(i * 2, L, M, Ln, Rn);
    if (ans != -1) return ans;
    return get(i * 2 + 1, M, R, Ln, Rn);
  }
  int get(int L, int R, long long _k) {
    k = _k;
    return get(1, 0, N, L, R);
  }
} box;
int sum(int a, int b) {
  a += b;
  return a < p ? a : a - p;
}
int mul(long long a, int b) { return a * b % p; }
struct seg_tree_with_mod {
  int t[N * 2 + 1];
  void change(int i, int v) {
    i += N;
    while (i > 0) {
      t[i] = sum(t[i], v);
      i >>= 1;
    }
  }
  int gets(int i, int L, int R, int Ln, int Rn) {
    if (Ln <= L && R <= Rn) {
      return t[i];
    }
    if (Rn <= L || R <= Ln) {
      return 0;
    }
    int M = (L + R) >> 1;
    return sum(gets(i * 2, L, M, Ln, Rn), gets(i * 2 + 1, M, R, Ln, Rn));
  }
} sumx[2];
const int RN = 1e9;
int n, m;
int a[N];
int w[N];
int main() {
  ios::sync_with_stdio(0);
  srand(time(0));
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> w[i];
    box.change(i, w[i]);
    sumx[0].change(i, mul(a[i] - i, w[i]));
    sumx[1].change(i, mul(RN + i + 1 - n - a[i], w[i]));
  }
  for (int i = 0; i < m; ++i) {
    int L, R;
    cin >> L >> R;
    if (L < 0) {
      L = -L - 1;
      int k = sum(R, p - w[L]);
      box.change(L, R - w[L]);
      sumx[0].change(L, mul(a[L] - L, k));
      sumx[1].change(L, mul(RN + L + 1 - n - a[L], k));
      w[L] = R;
    } else {
      --L;
      long long s = box.gets(1, 0, N, L, R);
      long long half = (s + 1) / 2;
      int M = box.get(L, R, half);
      long long sumL = half - box.k;
      long long sumR = s - sumL - w[M];
      long long wL = M - L >= 1 ? sumx[0].gets(1, 0, N, L, M) : 0;
      long long wR = R - M - 1 >= 1 ? sumx[1].gets(1, 0, N, M + 1, R) : 0;
      int coorL = a[M] + L - M, coorR = a[M] + R - M - 1;
      int curL = L, curR = RN + R + 1 - n - 1;
      int ans = sum(mul(sumL % p, sum(coorL, p - curL)), p - wL);
      if (M - L < 1) ans = 0;
      auto last = ans;
      if (R - M - 1 >= 1)
        ans = sum(ans, sum(mul(sumR % p, sum(curR, p - coorR)), p - wR));
      cout << ans << '\n';
    }
  }
}