#include<iostream> #include<cstring> #include <cstdio> #include <algorithm> using namespace std; #define ll long long ll b[105000]; int N; int lowbit(int x) { return x&(-x); } void upd(int x,ll val) { while(x<=N) { b[x]=min(b[x],val); x+=lowbit(x); } } ll query(int x) { ll res=(1LL<<60); while(x) { res=min(res,b[x]); x-=lowbit(x); } return res; } struct Point { int u,v,kind; ll ind; }p[400500]; bool cmp(Point left,Point right) { if(left.u==right.u && left.v==right.v) return left.kind<right.kind; if(left.u==right.u) return left.v<right.v; return left.u>right.u; } ll s[100500]; int ans[200500]; int main () { int n,m,q,u,v,ind; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<n;++i) scanf("%d",&ind),s[i+1]=ind+s[i]; for(int i=1;i<=m;++i) { scanf("%d%d%lld",&p[i].u,&p[i].v,&p[i].ind); p[i].kind=0; } scanf("%d",&q); for(int i=1;i<=q;++i) { scanf("%d%d",&p[m+i].u,&p[m+i].v); p[m+i].kind=1; p[m+i].ind=i; } sort(p+1,p+1+m+q,cmp); N=n; memset(ans,0,sizeof(ans)); memset(b,0,sizeof(b)); for(int i=1;i<=m+q;++i) { if(p[i].kind==0 && p[i].u<p[i].v) upd(p[i].v,p[i].ind-(s[p[i].v]-s[p[i].u])); if(p[i].kind==1 && p[i].u<p[i].v) ans[p[i].ind]=s[p[i].v]-s[p[i].u]+query(p[i].v); } for(int i=1;i<=n;++i) b[i]=(1LL<<60); for(int i=1;i<=m+q;++i) { if(p[i].kind==0 && p[i].u>p[i].v) upd(p[i].v,p[i].ind+(s[p[i].u]-s[p[i].v])); if(p[i].kind==1 && p[i].u>p[i].v) ans[p[i].ind]=query(p[i].v)-(s[p[i].u]-s[p[i].v]); } for(int i=1;i<=q;++i) printf("%dn",ans[i]); } return 0; }
