#include<bits/stdc++.h>
#define ll long long
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
ll ci(){
	ll x; scanf("%lld",&x); return x;
}

enum{N=2000023};

class UNI{
public:
	int fa[N];
	void init(int n){
		rep(i,1,n) fa[i] = i;
	}
	int fd(int x){
		return fa[x]==x ? x : fa[x]=fd(fa[x]);
	}
	int operator[](int x){ return fd(x); }
	bool merge(int x,int y){
		int fx=fd(x), fy=fd(y);
		if( fx!=fy ){
			fa[fx] = fy;
			return 1;
		} return 0;
	}
}uni;

using Set = set<pair<int,int> >;
Set st;
int tag = 0;

struct sth{
	int p, x, id;
	bool operator<(const sth&e) const {
		return p<e.p;
	}
}d[N];

Set::iterator I[N];
int ans[N];

int a[N];

signed main(){
	int T = ci();
	while( T-- ){
		int n = ci(), m = ci();
		rep(i,1,n) a[i] = ci();
		int tot = 0;
		rep(i,1,m){
			int l = ci(), r = ci(), x = ci();
			d[++tot] = {l,x,i};
			d[++tot] = {r,-1,i};
		}
		st.clear();
		st.insert({1e9,-1});
		tag = 0;
		sort(d+1, d+tot+1);
		int j = 1;
		uni.init(m);
		rep(i,1,n){
			tag += a[i];
			vector<pair<int,int> > v;
			while( st.begin()->first+tag < 0 ){
				v.push_back({st.begin()->first+tag-a[i], st.begin()->second});
				st.erase(st.begin());
			}
			for(auto o:v){
				int x = o.first, id = o.second;
		//printf("line %d: %d %d\n", __LINE__, x,id);
				auto it = st.lower_bound({x-tag, -1});
				if( it->first == x-tag ){
		//printf("line %d: %d %d merge %d\n", __LINE__, x,id, it->second);
					uni.merge(id, it->second);
				}else{
					I[id] = st.insert({x-tag,id}).first;
				}
			}
			while( j<=tot && d[j].p<=i ){
				int x = d[j].x, id = d[j].id;
		//printf("line %d: %d %d\n", __LINE__, x,id);
				if( x==-1 ){
					ans[id] = I[uni[id]]->first + tag;
				}else{
					auto it = st.lower_bound({x-tag, -1});
					if( it->first == x-tag ){
						uni.merge(id, it->second);
					}else{
						I[id] = st.insert({x-tag,id}).first;
					}
				}
				j++;
			}
		}
		rep(i,1,m) printf("%d\n", ans[i]);
	}
	return 0;
}