#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bi __int128
#define fi first
#define se second
#define pb push_back

const int N=1e5+5,B=320;
int n,m,bl[N],R[N],a[N],s[N];
struct Nod{
  int l,r;
  ll a,b,c;
}Q[N];
vector<int> G[N];

struct MinHull{
  int tp=0,st[N];

  bool chk(int x,int y,int z){return (bi)(a[z]-a[x])*(z-y)>=(bi)(a[z]-a[y])*(z-x);}

  void add(int i){
    while(tp>1&&chk(st[tp-1],st[tp],i)) --tp;
	st[++tp]=i;
  }

  int qry(ll x,ll y){
	int l=1,r=tp;
	while(l<r){
      int mid=((l+r)>>1);
	  if((bi)x*(st[mid+1]-st[mid])<(bi)y*(a[st[mid+1]]-a[st[mid]])) r=mid;
	  else l=mid+1;
	}
	return st[l];
  }
}Mn1,Mn2;

struct MaxHull{
  int tp=0,st[N];

  bool chk(int x,int y,int z){return (bi)(a[z]-a[x])*(z-y)<(bi)(a[z]-a[y])*(z-x);}

  void add(int i){
	if(tp&&a[i]<=a[st[tp]]) return;
	while(tp>1&&chk(st[tp-1],st[tp],i)) --tp;
	st[++tp]=i;
  }

  int qry(ll x,ll y){
	int l=1,r=tp;
    while(l<r){
	  int mid=((l+r)>>1);
	  if((bi)x*(st[mid+1]-st[mid])>(bi)y*(a[st[mid+1]]-a[st[mid]])) r=mid;
	  else l=mid+1;
	}
	return st[l];
  }
}Mx1,Mx2;

int Qmn(ll x,ll y){
  int pos=Mn1.qry(x,y);
  if(Mn2.tp){
	int tmp=Mn2.qry(x,y);
	if((bi)a[tmp]*y-(bi)x*tmp<(bi)a[pos]*y-(bi)x*pos) pos=tmp;
  }
  return pos;
}

int Qmx(ll x,ll y){
  int pos=Mx1.qry(x,y);
  if(Mx2.tp){
    int tmp=Mx2.qry(x,y);
	if((bi)a[tmp]*y-(bi)x*tmp>(bi)a[pos]*y-(bi)x*pos) pos=tmp;
  }
  return pos;
}

void build(int l,int r){
  Mn1.tp=Mx1.tp=0;
  for(int i=l;i<=r;i++) Mn1.add(i),Mx1.add(i);
}

int val(ll x,ll y){
  int pmn=Qmn(x,y),pmx=Qmx(x,y);
  if((bi)y*(a[pmx]-a[pmn])-(bi)x*(pmx-pmn)>=y){
	if(pmn>pmx) return -1;
	else if(pmn<pmx) return 1;
  }
  return 0;
}

pair<ll,ll> sol(ll a,ll b,ll c,ll d){
  int w=val(a+b,c+d);
  if(!w) return {a+b,c+d};

  if(w<0){
	int t=0;
	while(val((a<<(t+1))+b,(c<<(t+1))+d)==w) ++t;
	b+=(a<<t),d+=(c<<t);
    while(t){
	  --t;
	  if(val((a<<t)+b,(c<<t)+d)==w) b+=(a<<t),d+=(c<<t);
	}
  }else{
    int t=0;
	while(val(a+(b<<(t+1)),c+(d<<(t+1)))==w) ++t;
    a+=(b<<t),c+=(d<<t);
	while(t){
	  --t;
	  if(val(a+(b<<t),c+(d<<t))==w) a+=(b<<t),c+=(d<<t);
	}
  }
  return sol(a,b,c,d);
}

void wrk(int i){
  auto tmp=sol(0,1,1,0);ll x=tmp.fi,y=tmp.se;
  int pos=Qmx(x,y);
  Q[i].a=x,Q[i].c=y,Q[i].b=(ll)((bi)a[pos]*y-(bi)x*(pos-Q[i].l));
}

void SOLVE(){
  cin>>n;Mn2.tp=Mx2.tp=0;
  for(int i=1;i<=n;i++) cin>>a[i],bl[i]=(i-1)/B+1,R[bl[i]]=i;
  for(int i=2;i<=n;i++) s[i]=s[i-1]+(a[i]!=a[i-1]);
  
  cin>>m;
  for(int i=1;i<=m;i++){
    cin>>Q[i].l>>Q[i].r;
    if(s[Q[i].l]==s[Q[i].r]) Q[i].c=1,Q[i].a=0,Q[i].b=a[Q[i].l];
	else if(bl[Q[i].l]==bl[Q[i].r]) build(Q[i].l,Q[i].r),wrk(i);
	else G[bl[Q[i].l]].pb(i);
  }

  for(int i=1,r;i<=bl[n];i++){
    Mn2.tp=Mx2.tp=0,r=R[i];
	sort(G[i].begin(),G[i].end(),[&](int x,int y){return Q[x].r<Q[y].r;});

	for(auto j:G[i]){
      while(r<Q[j].r) ++r,Mx2.add(r),Mn2.add(r);
	  build(Q[j].l,R[i]),wrk(j);
	  
	}
	G[i].clear();
  }

  for(int i=1;i<=m;i++) cout<<Q[i].a<<' '<<Q[i].b<<' '<<Q[i].c<<'\n';
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int _;cin>>_;
  while(_--) SOLVE();
  return 0;
}