#include<bits/stdc++.h>
using namespace std;
struct node{ 
    long long p,s,c; 
}b[2505];
long long t,n,m,a[500005],f[105];
int main(){
	freopen("Stacks.in","r",stdin);
	freopen("Stacks.out","w",stdout);
    cin >> t;
    while(t --) 
	{ 
        cin >> n;
        for(int i = 1;i <= n; ++ i) cin >> a[i]; 
        cin >> m;
        int f1 = 1;
        for(int i = 1;i <= m; ++ i) 
		{
            cin >> b[i].p >> b[i].s >> b[i].c;
            if(b[i].s > 1) f1 = 0;
        }
        for(int i = 1;i <= n; ++ i) 
		{
            if(f1) 
			{
               	long long ans = 1e18;
                for(int j = 1;j <= m; ++ j) 
				{
                    if(b[j].p <= a[i]) ans = min(ans,b[j].c);
                }
                cout << (a[i] * ans) << ' ';
            } 
            else 
			{
                for(int j = 0;j <= 100; ++ j) f[j] = 1e18;
                f[0] = 0;
                for(int k = 1;k <= a[i]; ++ k) 
				{
                    long long ans = 1e18;
                    for(int j = 1;j <= m; ++ j) 
					{
                        if(k >= b[j].p) 
						{
                            if(k - min(b[j].s,k - b[j].p + 1) >= 0 && f[k - min(b[j].s,k - b[j].p + 1)] != 1e18) ans = min(ans,f[k - min(b[j].s,k - b[j].p + 1)] + b[j].c);
                        }
                    }
                    f[k] = ans;
                }
                cout << f[a[i]] << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}