#include<bits/stdc++.h>
using namespace std;
long long T,n,m,a[500005],p[2505],s[2505],c[2505],dp[2505][105];
struct mm{
    long long pp,ss,cc;
}b[2505];
bool cp(mm x,mm y){
    return x.cc<y.cc;
}
int main(){
    freopen("Stacks.in","r",stdin);
    freopen("Stacks.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        cin>>m;
        long long mx=0;
        for(int i=1;i<=m;i++) cin>>b[i].pp>>b[i].ss>>b[i].cc,mx=max(mx,b[i].ss);
        if(mx==1){
            sort(b+1,b+m+1,cp);
            for(int i=1;i<=n;i++){
                int ss=0;
                for(int j=1;j<=m;j++){
                    if(a[i]>=b[j].pp) ss+=b[j].cc*(a[i]-b[j].pp+1),a[i]=b[j].pp-1;
                }
                cout<<ss<<" ";
            }
            continue;
        }
        for(int i=0;i<=m;i++){
            for(int j=0;j<=100;j++){
                dp[i][j]=1e18;
            }
        }
        dp[0][0]=0;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=100;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=b[i].pp+b[i].ss-1) dp[i][j]=min(dp[i][j],dp[i][j-b[i].ss]+b[i].cc);
                else dp[i][j]=min(dp[i][j],dp[i][b[i].pp-1]+b[i].cc);
                
            }
        }
        for(int i=1;i<=n;i++) cout<<dp[m][a[i]]<<" ";
        cout<<"\n";
    }
    return 0;
}