#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
#define Bit(mask , i) ((mask >> i) & 1)
#define fi first
#define se second
#define _LOG2(nl) 31 - __builtin_clz(nl)
#define c_bit(nl) __builtin_popcount(nl)
#define ii pair<long long , int>
#define lll pair<long long , pair<long long , long long>>
#define lii pair<long long , pair<long long , int>>
#define iii pair<int , pair<int , int>>
#define iiii pair<pair<int , int> , pair<int , int>>
#define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
#define li pair<long long , int>
#define db long double
#define onBit(mask , i) (mask | (1 << i))
#define offBit(mask , i) (mask & (~(1 << i)))

const long long INF = 1e16;
const int N = 5e5 + 7;
const int M = 2e3 + 5e3 + 7;
const int S = 107;
vector<int> cand , query;
int n , m;
long long f[S * S] , ans[N];
long long Pre_res = 0;

struct gv{
    long long p , s , c;
};

gv b[M];

bool cmp(gv x , gv y){
    return x.p < y.p;
}

struct gv1{
    long long p;
    int id;
};

gv1 a[N];

bool cmp1(gv1 x , gv1 y){
    return x.p < y.p;
}

void inp(){
    cin >> n;
    for (int i = 1 ; i <= n ; ++i){
        cin >> a[i].p;
        a[i].id = i;
    }

    cin >> m;
    sort(a + 1 , a + n + 1 , cmp1);
    for (int i = 1 ; i <= m ; ++i){
        cin >> b[i].p >> b[i].s >> b[i].c;
    }
    sort(b + 1 , b + m + 1 , cmp);
}

void ktao(){
    for (int j = 1 ; j <= 100 * 101 ; ++j)
        f[j] = INF;

    f[0] = 0;
}

void sol(long long P , long long P1 , long long Wbest , long long Cbest){
    cout << P << " " << P1 << '\n';
    for (int i = 0 ; i < cand.size() ; ++i){
        cout << cand[i] << " ";
    }
    cout << '\n';
    for (int j = 1 ; j <= 100 * 101 ; ++j){
        for (int i = 0 ; i < cand.size() ; ++i){
            int id = cand[i];
            int W = min(b[id].s , P + j - b[id].p);
            if (f[j - W] == INF) continue;
            f[j] = min(f[j] , f[j - W] + b[id].c);
        }
    }

    for (int i = 0 ; i < query.size() ; ++i){
        int id = query[i];
        long long Pi = a[id].p;
        if (Pi - P + 1 > 100 * 100){
            long long tmp = Pi - P + 1 , k = (tmp - 100 * 100) / Wbest;
            long long res = Pre_res + k * Cbest + f[tmp - k * Wbest];

            ans[a[id].id] = Pre_res + res;
        }
        else ans[a[id].id] = Pre_res + f[Pi - P + 1];
    }
    long long Pi = P1 - 1;
    if (Pi - P + 1 > 100 * 100){
        long long tmp = Pi - P + 1 , k = (tmp - 100 * 100) / Wbest;
        long long res = Pre_res + k * Cbest + f[tmp - k * Wbest];

        Pre_res += res;
    }
    else Pre_res += f[Pi - P + 1];

    while (query.size()) query.pop_back();

    int i = 0;
    while (i < cand.size()){
        int id = cand[i];
        int W = min(b[id].s , P - b[id].p + 1);
        if (W == b[id].s) cand.erase(cand.begin() + i);
        else ++i;
    }
}

void solve(){
    ktao();
    int i = 1 , j = 1;
    b[m + 1].p = 1e9 + 1;
    long long Wbest = b[1].s , Cbest = b[1].c;
    while (j <= n){
        int u = i;

        cand.push_back(i);
        while (u < m && b[u + 1].p == b[i].p){
            ++u;
            cand.push_back(u);
            if (Cbest * b[u].s < b[u].c * Wbest){
                Wbest = b[u].s;
                Cbest = b[u].c;
            }
        }

        if (j < b[u + 1].p){
            int v = j;
            query.push_back(j);
            while (v < n && a[v + 1].p < b[u + 1].p){
                ++v;
                query.push_back(v);
            }
            j = v + 1;
        }

        sol(b[i].p , b[u + 1].p , Wbest , Cbest);
        i = u + 1;
    }

    for (int i = 1 ; i <= n ; ++i){
        cout << ans[i] << " ";
    }
    cout << '\n';
}

int main(){
    faster;
    inp();
    solve();
    return 0;
}