description: You are given two integer arrays of length N, A1 and A2. You are also given Q queries of 4 types: 
  
  1 k l r x: set Ak_i:=min(Ak_i, x) for each l ≤ i ≤ r.
  
  2 k l r x: set Ak_i:=max(Ak_i, x) for each l ≤ i ≤ r.
  
  3 k l r x: set Ak_i:=Ak_i+x for each l ≤ i ≤ r.
  
  4 l r: find the (∑_{i=l}^r F(A1_i+A2_i)) \% (10^9+7) where F(k) is the k-th Fibonacci number (F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)), and x \% y denotes the remainder of the division of x by y.
  
  You should process these queries and answer each query of the fourth type.
  
  Input
  
  The first line contains two integers N and Q. (1 ≤ N, Q ≤ 5 × 10^4) 
  
  The second line contains N integers, array A1_1, A1_2, ... A1_N. (0 ≤ A1_i ≤ 10^6)
  
  The third line contains N integers, array A2_1, A2_2, ... A2_N. (0 ≤ A2_i ≤ 10^6)
  
  The next Q lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. (k ∈ \{1, 2\}, 1 ≤ l ≤ r ≤ N)
  
  For queries of type 1 and 2, 0 ≤ x ≤ 10^9 holds.
  
  For queries of type 3, −10^6 ≤ x ≤ 10^6 holds.
  
  It is guaranteed that after every query each number in arrays A1 and A2 will be nonnegative. 
  
  Output
  
  Print the answer to each query of the fourth type, in separate lines. 
  
  Examples
  
  Input
  
  
  3 4
  1 0 2
  2 1 0
  4 1 3
  3 2 2 2 3
  1 1 1 3 0
  4 1 3
  
  
  Output
  
  
  4
  4
  
  
  Input
  
  
  5 4
  1 3 5 3 2
  4 2 1 3 3
  4 1 3
  4 2 5
  2 1 2 4 6
  4 2 4
  
  
  Output
  
  
  18
  26
  68
  
  Note
  
  In the first example: The answer for the first query is F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4. After the second query, the array A2 changes to [2, 4, 0]. After the third query, the array A1 changes to [0, 0, 0]. The answer for the fourth query is F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4. 
  
  In the second example: The answer for the first query is F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18. The answer for the second query is F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26. After the third query, the array A1 changes to [1, 6, 6, 6, 2]. The answer for the fourth query is F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68. 
solution: #include <bits/stdc++.h>
  using namespace std;
  using LL = long long;
  const int P = 1e9 + 7;
  int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
  int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
  int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
  void uad(int& k1, int k2) { k1 += k2 - P, k1 += k1 >> 31 & P; }
  void usu(int& k1, int k2) { k1 -= k2, k1 += k1 >> 31 & P; }
  template <typename... T>
  int ad(int k1, T... k2) {
    return ad(k1, ad(k2...));
  }
  template <typename... T>
  int su(int k1, T... k2) {
    return su(k1, ad(k2...));
  }
  template <typename... T>
  int mu(int k1, T... k2) {
    return mu(k1, mu(k2...));
  }
  template <typename... T>
  void uad(int& k1, T... k2) {
    return uad(k1, ad(k2...));
  }
  template <typename... T>
  void usu(int& k1, T... k2) {
    return usu(k1, ad(k2...));
  }
  int po(int k1, int k2) {
    int k3 = 1;
    for (; k2; k2 >>= 1, k1 = mu(k1, k1))
      if (k2 & 1) k3 = mu(k3, k1);
    return k3;
  }
  template <typename T>
  void rd(T& x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) f ^= !(c ^ 45);
    x = (c & 15);
    while (isdigit(c = getchar())) x = x * 10 + (c & 15);
    if (f) x = -x;
  }
  template <typename T>
  void pt(T x, int c = -1) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) pt(x / 10);
    putchar(x % 10 + 48);
    if (c != -1) putchar(c);
  }
  const LL INFLL = 0X3F3F3F3F3F3F3F3FLL;
  const int N = 50005;
  int n, Q, a[2][N];
  struct mat {
    int a[2][2];
    mat operator*(const mat& b) const {
      mat c;
      for (int i = (0); i <= (1); ++i)
        for (int j = (0); j <= (1); ++j)
          c.a[i][j] = (1LL * a[i][0] * b.a[0][j] + 1LL * a[i][1] * b.a[1][j]) % P;
      return c;
    }
    mat operator+(const mat& b) const {
      mat c;
      for (int i = (0); i <= (1); ++i)
        for (int j = (0); j <= (1); ++j) c.a[i][j] = ad(a[i][j], b.a[i][j]);
      return c;
    }
    mat operator-(const mat& b) const {
      mat c;
      for (int i = (0); i <= (1); ++i)
        for (int j = (0); j <= (1); ++j) c.a[i][j] = su(a[i][j], b.a[i][j]);
      return c;
    }
    mat operator*(const int& k) const {
      mat c;
      for (int i = (0); i <= (1); ++i)
        for (int j = (0); j <= (1); ++j) c.a[i][j] = mu(a[i][j], k);
      return c;
    }
    mat inv() const {
      const int I =
          po(((1LL * a[0][0] * a[1][1] - 1LL * a[0][1] * a[1][0]) % P + P) % P,
             P - 2);
      return (mat){{{a[1][1], su(0, a[0][1])}, {su(0, a[1][0]), a[0][0]}}} * I;
    }
    void operator+=(const mat& k) {
      for (int i = (0); i <= (1); ++i)
        for (int j = (0); j <= (1); ++j) uad(a[i][j], k.a[i][j]);
    }
  } base = (mat){{{1, 1}, {1, 0}}};
  mat get_mat(LL k) {
    if (k < 0) {
      return get_mat(-k).inv();
    }
    mat res = (mat){{{1, 0}, {0, 1}}};
    mat w = base;
    while (k) {
      if (k & 1) {
        res = res * w;
      }
      k >>= 1;
      if (k) w = w * w;
    }
    return res;
  }
  struct fibint {
    LL x;
    mat mt;
    bool operator<(const fibint& k) const { return x < k.x; }
    bool operator>(const fibint& k) const { return x > k.x; }
    bool operator<=(const fibint& k) const { return x <= k.x; }
    bool operator>=(const fibint& k) const { return x >= k.x; }
    bool operator==(const fibint& k) const { return x == k.x; }
    bool operator!=(const LL& k) const { return x != k; }
    fibint operator+(const fibint& k) const {
      return (fibint){x + k.x, mt * k.mt};
    }
    fibint operator-(const fibint& k) const {
      return (fibint){x - k.x, mt * k.mt.inv()};
    }
    void operator+=(const fibint& k) { x += k.x, mt = mt * k.mt; }
  };
  struct segment_tree_beats {
    struct data {
      fibint mx, mx2, mn, mn2, tmx, tmn, tad;
      int cmx, cmn;
      mat sum;
    } t[N * 4];
    void pushup(int u) {
      const int lu = u << 1, ru = u << 1 | 1;
      t[u].sum = t[lu].sum + t[ru].sum;
      if (t[lu].mx == t[ru].mx) {
        t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx + t[ru].cmx;
        t[u].mx2 = max(t[lu].mx2, t[ru].mx2);
      } else if (t[lu].mx > t[ru].mx) {
        t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx;
        t[u].mx2 = max(t[lu].mx2, t[ru].mx);
      } else {
        t[u].mx = t[ru].mx, t[u].cmx = t[ru].cmx;
        t[u].mx2 = max(t[lu].mx, t[ru].mx2);
      }
      if (t[lu].mn == t[ru].mn) {
        t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn + t[ru].cmn;
        t[u].mn2 = min(t[lu].mn2, t[ru].mn2);
      } else if (t[lu].mn < t[ru].mn) {
        t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn;
        t[u].mn2 = min(t[lu].mn2, t[ru].mn);
      } else {
        t[u].mn = t[ru].mn, t[u].cmn = t[ru].cmn;
        t[u].mn2 = min(t[lu].mn, t[ru].mn2);
      }
    }
    void push_add(int u, int l, int r, fibint v) {
      t[u].sum = t[u].sum * v.mt;
      t[u].mx += v, t[u].mn += v;
      if (t[u].mx2 != -INFLL) t[u].mx2 += v;
      if (t[u].mn2 != INFLL) t[u].mn2 += v;
      if (t[u].tmx != -INFLL) t[u].tmx += v;
      if (t[u].tmn != INFLL) t[u].tmn += v;
      t[u].tad += v;
    }
    void push_min(int u, fibint tg) {
      if (t[u].mx <= tg) return;
      t[u].sum += (tg.mt - t[u].mx.mt) * t[u].cmx;
      if (t[u].mn2 == t[u].mx) t[u].mn2 = tg;
      if (t[u].mn == t[u].mx) t[u].mn = tg;
      if (t[u].tmx > tg) t[u].tmx = tg;
      t[u].mx = tg, t[u].tmn = tg;
    }
    void push_max(int u, fibint tg) {
      if (t[u].mn > tg) return;
      t[u].sum += (tg.mt - t[u].mn.mt) * t[u].cmn;
      if (t[u].mx2 == t[u].mn) t[u].mx2 = tg;
      if (t[u].mx == t[u].mn) t[u].mx = tg;
      if (t[u].tmn < tg) t[u].tmn = tg;
      t[u].mn = tg, t[u].tmx = tg;
    }
    void pushdown(int u, int l, int r) {
      const int lu = u << 1, ru = u << 1 | 1, mid = (l + r) >> 1;
      if (t[u].tad.x)
        push_add(lu, l, mid, t[u].tad), push_add(ru, mid + 1, r, t[u].tad);
      if (t[u].tmx != -INFLL) push_max(lu, t[u].tmx), push_max(ru, t[u].tmx);
      if (t[u].tmn != INFLL) push_min(lu, t[u].tmn), push_min(ru, t[u].tmn);
      t[u].tad = (fibint){0, (mat){{{1, 0}, {0, 1}}}},
      t[u].tmx = (fibint){-INFLL, (mat){{{0, 0}, {0, 0}}}},
      t[u].tmn = (fibint){INFLL, (mat){{{0, 0}, {0, 0}}}};
    }
    void build(int* a, int u = 1, int l = 1, int r = n) {
      t[u].tmn = (fibint){INFLL, (mat){{{0, 0}, {0, 0}}}},
      t[u].tmx = (fibint){-INFLL, (mat){{{0, 0}, {0, 0}}}};
      t[u].tad = (fibint){0, (mat){{{1, 0}, {0, 1}}}};
      if (l == r) {
        t[u].mx = t[u].mn = (fibint){a[l], t[u].sum = get_mat(a[l])};
        t[u].mx2 = (fibint){-INFLL, (mat){{{0, 0}, {0, 0}}}},
        t[u].mn2 = (fibint){INFLL, (mat){{{0, 0}, {0, 0}}}};
        t[u].cmx = t[u].cmn = 1;
        return;
      }
      int mid = (l + r) >> 1;
      build(a, u << 1, l, mid), build(a, u << 1 | 1, mid + 1, r);
      pushup(u);
    }
    void add(int L, int R, const fibint& v, int u = 1, int l = 1, int r = n) {
      if (R < l || r < L) return;
      if (L <= l && r <= R) return push_add(u, l, r, v);
      int mid = (l + r) >> 1;
      pushdown(u, l, r);
      add(L, R, v, u << 1, l, mid), add(L, R, v, u << 1 | 1, mid + 1, r);
      pushup(u);
    }
    void tomin(int L, int R, const fibint& v, int u = 1, int l = 1, int r = n) {
      if (R < l || r < L || t[u].mx <= v) return;
      if (L <= l && r <= R && t[u].mx2 < v) return push_min(u, v);
      int mid = (l + r) >> 1;
      pushdown(u, l, r);
      tomin(L, R, v, u << 1, l, mid), tomin(L, R, v, u << 1 | 1, mid + 1, r);
      pushup(u);
    }
    void tomax(int L, int R, const fibint& v, int u = 1, int l = 1, int r = n) {
      if (R < l || r < L || t[u].mn >= v) return;
      if (L <= l && r <= R && t[u].mn2 > v) return push_max(u, v);
      int mid = (l + r) >> 1;
      pushdown(u, l, r);
      tomax(L, R, v, u << 1, l, mid), tomax(L, R, v, u << 1 | 1, mid + 1, r);
      pushup(u);
    }
    mat qsum(int L, int R, int u = 1, int l = 1, int r = n) {
      if (R < l || r < L) return (mat){{{0, 0}, {0, 0}}};
      if (L <= l && r <= R) return t[u].sum;
      int mid = (l + r) >> 1;
      pushdown(u, l, r);
      return qsum(L, R, u << 1, l, mid) + qsum(L, R, u << 1 | 1, mid + 1, r);
    }
  } t[2];
  mat ans;
  void sol(int k1, int k2, int k3, int k4, int k5) {
    if (k2 > k5 || k3 < k4) return;
    if (k4 <= k2 && k3 <= k5) {
      if (t[0].t[k1].mn == t[0].t[k1].mx) {
        ans += t[0].t[k1].mn.mt * t[1].t[k1].sum;
        return;
      } else if (t[1].t[k1].mn == t[1].t[k1].mx) {
        ans += t[1].t[k1].mn.mt * t[0].t[k1].sum;
        return;
      }
    }
    t[0].pushdown(k1, k2, k3), t[1].pushdown(k1, k2, k3);
    int mid = (k2 + k3) >> 1;
    sol(k1 * 2, k2, mid, k4, k5), sol(k1 * 2 + 1, mid + 1, k3, k4, k5);
  }
  int main() {
    rd(n), rd(Q);
    for (int i = (1); i <= (n); ++i) rd(a[0][i]);
    for (int i = (1); i <= (n); ++i) rd(a[1][i]);
    for (int i = (0); i <= (1); ++i) {
      t[i].build(a[i]);
    }
    for (int _ = (1); _ <= (Q); ++_) {
      int opt;
      rd(opt);
      if (opt == 1) {
        int k, l, r, x;
        rd(k), rd(l), rd(r), rd(x);
        --k;
        t[k].tomin(l, r, (fibint){x, get_mat(x)});
      } else if (opt == 2) {
        int k, l, r, x;
        rd(k), rd(l), rd(r), rd(x);
        --k;
        t[k].tomax(l, r, (fibint){x, get_mat(x)});
      } else if (opt == 3) {
        int k, l, r, x;
        rd(k), rd(l), rd(r), rd(x);
        --k;
        t[k].add(l, r, (fibint){x, get_mat(x)});
      } else {
        int l, r;
        rd(l), rd(r);
        ans = (mat){{{0, 0}, {0, 0}}};
        sol(1, 1, n, l, r);
        printf("%d\n", ans.a[0][1]);
      }
    }
    return 0;
  }
  