paimon seg tree

//misaka and rin will carry me to cm
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <tuple>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()

#define LC(k) (2*(k) +1)
#define RC(k) (2*(k) +2)

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1;
const int MX = 5e4 +10, int_max = 0x3f3f3f3f;

using namespace std;

//i will learn from moo.
/* Input */
template<class T> void read(T &x) { cin >> x; }
template<class H, class T> void read(pair<H, T> &p) { cin >> p.first >> p.second; }
template<class T, size_t S> void read(array<T, S> &a) { for (T &i : a) read(i); }
template<class T> void read(vector<T> &v) { for (T &i : v) read(i); }

template<class H, class... T> void read(H &h, T &...t) { read(h); read(t...); }

/* Output */
template<class H, class T> ostream &operator<<(ostream &o, pair<H, T> &p) { o << p.first << " " << p.second; return o; }
template<class T, size_t S> ostream &operator<<(ostream &o, array<T, S> &a) { string s; for (T i : a) o << s << i, s = " "; return o; }
template<class T> ostream &operator<<(ostream &o, vector<T> &v) { string s; for (T i : v) o << s << i, s = " "; return o; }

template<class T> void write(T x) { cout << x; }
template<class H, class... T> void write(const H &h, const T &...t) { write(h); write(t...); }

void print() { write('\n'); }
template<class H, class... T> void print(const H &h, const T &...t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

/* Misc */
template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); }

ll sq(ll a){
    return ((a%mod)*(a%mod))%mod;
}

struct matrix{
    unsigned arr[4][4];
    int t;
    matrix(){
        t = 0;
        memset(arr, 0, sizeof(arr));
    }
    matrix(int a){
        //t = a;
        t = 0;
        memset(arr, 0, sizeof(arr));
        for(int i = 0; i<4; i++) arr[i][i] = 1;
        arr[0][1] = a;
        arr[1][2] = arr[1][3] = (2*a)%mod;
        arr[0][2] = arr[0][3] = sq(a);
        arr[2][3] = 1;
        /**
         * 1 a a*a a*a
         * 0 1 2*a 2*a
         * 0 0 1   1
         * 0 0 0   1
        **/
    }
    matrix(int a, int b, int c, int d){
        memset(arr, 0, sizeof(arr));
        arr[0][0] = a;
        arr[0][1] = b;
        arr[0][2] = c;
        arr[0][3] = d;
    }
    matrix operator*(const matrix& b) const{
        if(b.t == 1) return *this;
        if(t == 1) return b;
        matrix c = matrix();
        //int ttt[4];
        for(int i = 0; i<4; i++){
            //for(int j =0; j<4; j++) ttt[j] = arr[i][j];
            for(int j = i; j<4; j++){
                for(int k = 0; k<=j; k++){
                    (c.arr[i][j] += ((ll)arr[i][k]*(ll)b.arr[k][j])%mod);
                }
            }
        }
        for(int i = 0; i<4; i++){
            for(int j = i; j<4; j++){
                c.arr[i][j] %= mod;
            }
        }
        return c;
    }
    matrix operator+(const matrix&b) const{
        matrix c = matrix();
        //for(int i = 0; i<4; i++){
            for(int j = 0; j<4; j++){
                c.arr[0][j] = (arr[0][j]+b.arr[0][j])%mod;
            }
        //}
        return c;
    }
    void pr(){
        for(int i = 0; i<4; i++){
            for(int j = 0; j<4; j++){
                write(arr[i][j], ' ');
            }
            print();
        }
    }
} st[MX*4], tag[MX*4], dummy, emp;



void push(int k, int L, int R){
    //if(R - L > 1){
        tag[LC(k)] = tag[LC(k)] * tag[k];
        st[LC(k)] = st[LC(k)] * tag[k];
        tag[RC(k)] = tag[RC(k)] * tag[k];
        st[RC(k)] = st[RC(k)] * tag[k];
        //st[k] = st[k] * tag[k];
        tag[k] = dummy;

    //}
}

void U(int qL, int qR, const matrix& v, int k, int L, int R){
    if(qR <= L || R <= qL || R <= L) return ;
    if(qL <= L && R <= qR){
        tag[k] = tag[k] * v;
        st[k] = st[k] * v;
        return ;
    }
    push(k, L, R);
    int mid = (L + R)/2;
    U(qL, qR, v, LC(k), L, mid);
    U(qL, qR, v, RC(k), mid, R);
    st[k] = st[LC(k)] + st[RC(k)];
    //st[k] = (st[LC(k)] * tag[LC(k)]) + (st[RC(k)] * tag[RC(k)]);
    //st[k].pr();
}

ll S(int qL, int qR, int k, int L, int R){
    if(qR <= L || R <= qL || R <= L) return 0;
    if(qL <= L && R <= qR) return st[k].arr[0][3];

    push(k, L, R);
    int mid = (L + R)/2;
    return (S(qL, qR, LC(k), L, mid) + S(qL, qR, RC(k), mid, R))%mod;
}

ll arr[MX], n, m, q, s = 1;
ll ans[MX];
vector<pair<int, pair<int, int>>> adj[MX], upp;

void build(){
    dummy = matrix(0);
    dummy.t = 1;
    emp = matrix(0);
    dummy.arr[2][3] = 0;
    while(s <= n) s*=2;
    for(int i = s - 1; i<s*2 -1; i++){
        st[i] = matrix(1, arr[i-(s-1)], sq(arr[i-(s-1)]), sq(arr[i-(s-1)]));
        tag[i] = dummy;
    }
    for(int i = s - 2; ~i; i--){
        st[i] = st[LC(i)] + st[RC(i)];
        tag[i] = dummy;
        //st[i].pr();
    }
}

#define le second.first
#define ri second.second
#define val first
#define abs(x) ((x) > 0 ? (x) : (-(x)))
#define mt(a, b, c) make_pair(c, make_pair(a, b))
void solve(){
    read(n, m, q);
    for(int i = 0; i<n; i++){
        read(arr[i]);
        (arr[i] += mod) %= mod;
    }
    build();
    //[>*
    for(int i = 0; i<m; i++){
        int a, b, c; read(a, b, c);
        (c += mod) %= mod;
        upp.push_back(mt(a, b, c));
    }
    for(int i = 1; i<=q; i++){
        int a, b, c, d; read(a, b, c, d);
        if(c-1 >= 0) adj[c-1].push_back(mt(a, b, -i));
        adj[d].push_back(mt(a, b, i));
    }
    for(int i = 0; i<=m; i++){
        //print("update# ", i);
        for(auto& e : adj[i]){
            //print(e, S(e.le-1, e.ri, 0, 0, s), abs(e.val), e.val/abs(e.val), mod - ans[abs(e.val)]);
            ans[abs(e.val)] += mod + (e.val/abs(e.val))*S(e.le-1, e.ri, 0, 0, s);
        }

        if(i <m){
            //print(upp[i]);
            matrix v = matrix(upp[i].val);
            //v.pr();
            U(upp[i].le - 1, upp[i].ri, v, 0, 0, s);
            U(0, upp[i].le-1, emp, 0, 0, s);
            U(upp[i].ri, s, emp, 0, 0, s);
        }
    }
    for(int i = 1; i<=q; i++){
        print(ans[i]%mod);
    }
    //**/
    /*8
    while(q--){
        int op, l, r; read(op, l, r);
        if(op == 1){
            int a; read(a);
            matrix v = matrix(a);
            v.pr();
            dummy.pr();
            U(l-1, r, v, 0, 0, s);
            U(0, l-1, 0, 0, 0, s);
            U(r+1, s, 0, 0, 0, s);
        }else{
            print(S(l-1, r, 0, 0, s));
        }
    }
    **/
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);
    int T = 1;
    //cin >> T;
  while(T--){
        solve();
    }
    return 0;
}