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. 
10 10
570803 970709 848133 22452 695639 737666 285474 739600 16759 171950
145477 412167 876550 948646 26198 140802 68907 620239 834307 776372
1 1 4 8 412290830
4 4 6
4 2 2
4 7 10
4 2 8
4 5 7
4 3 4
4 8 9
4 6 8
4 3 4
 1 1
40
40
4 1 1

290830112
495006418
106843172
850178361
249186967
441860838
827699421
601638210
441860838
 184550589

// Retired?
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = long unsigned long;
using ld = double long;

template<int m>
struct modint {
    unsigned x;

    modint() : x(0) {}
    modint(long long arg) : x((arg %= m) < 0 ? arg + m : arg) {}

    modint operator+ (const modint& b) const {
        auto t = *this; t.x = (t.x += b.x) >= m ? t.x-m : t.x; return t;
    }

    modint operator- (const modint& b) const {
        auto t = *this; t.x = (t.x += m-b.x) >= m ? t.x-m : t.x; return t;
    }

    modint operator* (const modint& b) const {
        auto t = *this; t.x = ll(t.x) * b.x % m; return t;
    }

    modint operator/ (const modint& b) const {
        return *this * b.inv();
    }

    template<class T> modint operator^ (T n) const {
        modint t;
        if (n == 0) return t.x = 1, t;
        if (n == 1) return t.x = x, t;
        t = *this ^ (n >> 1); t *= t;
        return n & 1 ? *this * t : t;
    }

    modint& operator+= (const modint& b) { return *this = *this + b; }
    modint& operator-= (const modint& b) { return *this = *this - b; }
    modint& operator*= (const modint& b) { return *this = *this * b; }
    modint& operator/= (const modint& b) { return *this = *this / b; }
    modint& operator++ () { if (++x == m) x = 0; return *this; }
    modint& operator-- () { if (x-- == 0) x = m-1; return *this; }
    modint operator++ (int) { modint tmp = *this; ++*this; return tmp; }
    modint operator-- (int) { modint tmp = *this; --*this; return tmp; }
    bool operator== (const modint& other) const { return x == other.x; }
    bool operator!= (const modint& other) const {	return x != other.x; }
    int operator() () const { return x; }
    template<class T> modint operator^= (T n) { return *this = *this ^ n; }
    modint inv() const { return *this ^ (m-2); }
};

const int mod = 1'000'000'007;
typedef modint<mod> mint;

template<class R>
struct matrix {
    inline static constexpr int n = 2;
    inline static constexpr int m = 2;
    array<R, 4> a;

    static matrix eye() {
        matrix t;
        for (int i=0; i<n; i++)
            t[i][i] = 1;
        return t;
    }

    matrix operator* (const matrix& b) const {
        matrix c;
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++)
                for (int k=0; k<b.m; k++)
                    c[i][k] += a[m*i+j] * b[j][k];
        return c;
    }

    matrix& operator+= (const matrix& b) {
        for (int i=0; i<n*m; i++)
            a[i] += b.a[i];
        return *this;
    }

    matrix& operator-= (const matrix& b) {
        for (int i=0; i<n*m; i++)
            a[i] += b.a[i];
        return *this;
    }

    R* operator[] (int x) { return a.data() + m*x; }
    const R* operator[] (int x) const { return a.data() + m*x; }
    matrix operator+ (const matrix& b) const { auto t = *this; t += b; return t; }
    matrix operator- (const matrix& b) const { auto t = *this; t -= b; return t; }
    matrix& operator*= (const matrix& b) { return *this = *this * b; }
    template<class U> matrix operator^= (U arg) { return *this = *this ^ arg; }

    template<class U>
    matrix operator^ (U arg) const {
        if (arg == 0)
            return matrix::eye();
        if (arg == 1)
            return *this;
        auto t = *this ^ (arg >> 1);
        t *= t;
        if (arg & 1)
            t *= *this;
        return t;
    }

    matrix T() const {
        matrix b(m, n);
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++)
                b[j][i] = a[i][j];
        return b;
    }
};

using minimat = matrix<mint>;
const minimat fib = []() {
    minimat a;
    a[0][1] = a[1][0] = a[1][1] = 1;
    return a;
}();

const minimat fib_inv = []() {
    minimat a;
    a[0][0] = -1;
    a[0][1] = a[1][0] = 1;
    return a;
}();

template<class T, class U, class F, class G, class H>
struct segtreelazy {
    struct node { T v; U u; };
    int maxn;
    vector<node> a;
    T e; U eu;
    F f; G g; H h;
    // Add two elements
    // Add two updaters
    // Add an element and an update
    // Neutral element
    // Neutral update
    // Bottom level element
    segtreelazy(int n, F f, G g, H h, T e = T(), U eu = U(), T v = T()) :
        e(e), eu(eu), f(f), g(g), h(h)
    {
        maxn = 1;
        while (maxn < n)
            maxn <<= 1;
        a.assign(2*maxn, node{v, eu});
        for (int i=maxn-1; i; i--)
            a[i].v = f(a[2*i].v, a[2*i+1].v);
    }

    void push(int x) {
        a[x].v = h(a[x].v, a[x].u);
        if (x < maxn) {
            a[2*x  ].u = g(a[2*x  ].u, a[x].u);
            a[2*x+1].u = g(a[2*x+1].u, a[x].u);
        }
        a[x].u = eu;
    }

    void set(int p, const T& v) {
        int x = 1, xl = 0, xr = maxn;
        while (xr-xl > 1) {
            push(x);
            int xm = (xl+xr) >> 1;
            (p < xm ? xr : xl) = xm;
            x = 2*x + (p >= xm);
        }
        a[x] = {v, eu};
        do {
            push(x^1);
            x >>= 1;
            a[x].v = f(a[2*x].v, a[2*x+1].v);
        } while (x > 1);
    }

    void update(int l, int r, const U& u, int x, int xl, int xr) {
        if (r <= xl || xr <= l)
            return push(x);
        if (l <= xl && xr <= r)
            return a[x].u = g(a[x].u, u), push(x);
        push(x);
        int xm = (xl+xr) >> 1;
        update(l, r, u, 2*x  , xl, xm);
        update(l, r, u, 2*x+1, xm, xr);
        a[x].v = f(a[2*x].v, a[2*x+1].v);
    }

    T get(int l, int r, int x, int xl, int xr) {
        push(x);
        if (r <= xl || xr <= l)
            return e;
        if (l <= xl && xr <= r)
            return a[x].v;
        int xm = (xl+xr) >> 1;
        return f(get(l, r, 2*x, xl, xm), get(l, r, 2*x+1, xm, xr));
    }

    void update(int l, int r, const U& u) { update(l, r, u, 1, 0, maxn); }
    T operator() (int l, int r) { return get(l, r, 1, 0, maxn); }
};

segtreelazy stlz(
    50005,
    plus<minimat>(),
    plus<ll>(),
    [](minimat a, ll b) {
        if (b == 0) return a;
        if (b > 0) return a * (fib ^ b);
        return a * (fib_inv ^ (-b));
    },
    minimat{},
    0,
    minimat::eye()
);

template<class CB>
struct segtreebeats {
    struct node {ll lo, hi, lz; };
    int maxn;
    vector<node> a;
    CB cb;

    segtreebeats(int n, CB cb) : cb(cb) {
        maxn = 1;
        while (maxn < n)
            maxn <<= 1;
        a.assign(2*maxn, node{0, 0, 0});
    }

    void push(int x) {
        a[x].lo += a[x].lz;
        a[x].hi += a[x].lz;
        if (x < maxn) {
            a[2*x  ].lz = a[x].lz;
            a[2*x+1].lz = a[x].lz;
        }
        a[x].lz = 0;
    }

    void pull(int x) {
        a[x].lo = min(a[2*x].lo, a[2*x+1].lo);
        a[x].hi = max(a[2*x].hi, a[2*x+1].hi);
    }

    void add_delta(int l, int r, ll u, int x, int xl, int xr) {
        if (r <= xl || xr <= l)
            return push(x);
        if (l <= xl && xr <= r)
            return a[x].lz += u, push(x), cb(xl, xr, u);
        push(x);
        int xm = (xl+xr) >> 1;
        add_delta(l, r, u, 2*x  , xl, xm);
        add_delta(l, r, u, 2*x+1, xm, xr);
        pull(x);
    }

    void max_set(int l, int r, ll u, int x, int xl, int xr) {
        if (r <= xl || xr <= l)
            return push(x);

        if (l <= xl && xr <= r && a[x].hi == a[x].lo) {
            push(x);
            ll d = max(u, a[x].hi) - a[x].hi; 
            return a[x].lz += d, push(x), cb(xl, xr, d);
        }
        
        push(x);
        int xm = (xl+xr) >> 1;
        max_set(l, r, u, 2*x  , xl, xm);
        max_set(l, r, u, 2*x+1, xm, xr);
        pull(x);
    }

    void min_set(int l, int r, ll u, int x, int xl, int xr) {
        if (r <= xl || xr <= l)
            return push(x);

        if (l <= xl && xr <= r && a[x].hi == a[x].lo) {
            push(x);
            ll d = min(u, a[x].hi) - a[x].hi; 
            return a[x].lz += d, push(x), cb(xl, xr, d);
        }
        
        push(x);
        int xm = (xl+xr) >> 1;
        min_set(l, r, u, 2*x  , xl, xm);
        min_set(l, r, u, 2*x+1, xm, xr);
        pull(x);
    }

    void add_delta(int l, int r, ll u) { add_delta(l, r, u, 1, 0, maxn); }
    void max_set(int l, int r, ll u) { max_set(l, r, u, 1, 0, maxn); }
    void min_set(int l, int r, ll u) { min_set(l, r, u, 1, 0, maxn); }

};

void cb(int l, int r, ll d) {
    stlz.update(l, r, d);
}

int main() {
    ios::sync_with_stdio(!cin.tie(0));

    int n, q;
    cin >> n >> q;

    segtreebeats stb1(n+1, cb), stb2(n+1, cb);

    for (int i=1; i<=n; i++) {
        int x;
        cin >> x;
        stb1.add_delta(i, i+1, x);
    }

    for (int i=1; i<=n; i++) {
        int x;
        cin >> x;
        stb2.add_delta(i, i+1, x);
    }
    
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int k, l, r, x;
            cin >> k >> l >> r >> x;
            (k == 1 ? stb1 : stb2).min_set(l, r+1, x);
        } else if (t == 2) {
            int k, l, r, x;
            cin >> k >> l >> r >> x;
            (k == 1 ? stb1 : stb2).max_set(l, r+1, x);
        } else if (t == 3) {
            int k, l, r, x;
            cin >> k >> l >> r >> x;
            (k == 1 ? stb1 : stb2).add_delta(l, r+1, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << stlz(l, r+1)[0][1]() << '\n';
        }
    }
}