#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=2e5+10; int a[N]; int l1[N],r1[N],l2[N],r2[N]; int rk[N],p[N]; int n,q; long long cost=0; vector<int> vec[N]; vector<int> ask1[N],ask2[N]; int ans[N],to[N]; struct segtree{ #define ls p<<1 #define rs p<<1|1 #define mid ((l+r)>>1) int T[N<<2]; void pu(int p){ T[p]=max(T[ls],T[rs]); } void bd(int p,int l,int r){ if(l==r) return T[p]=rk[l],void(); bd(ls,l,mid);bd(rs,mid+1,r);pu(p); } void upd(int p,int l,int r,int x,int v){ if(l==r) return T[p]=v,void(); if(x<=mid) upd(ls,l,mid,x,v); else upd(rs,mid+1,r,x,v);pu(p); } int res=0; void _qry(int p,int l,int r,int pl,int pr){ if(T[p]<=res) return ; if(pl<=l&&r<=pr) return res=(T[p]>res)?T[p]:res,void(); if(pl<=mid) _qry(ls,l,mid,pl,pr); if(pr>mid) _qry(rs,mid+1,r,pl,pr); } inline int qry(int p,int l,int r,int pl,int pr){ res=0;_qry(p,l,r,pl,pr); return res; } }sgt1,sgt2; int main(){ //freopen("max.in","r",stdin); //freopen("max.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) p[i]=i; sort(p+1,p+n+1,[&](int x,int y){return a[x]<a[y];}); int cnt=1; for(int i=1;i<=n;i++){ rk[p[i]]=cnt;to[cnt]=a[p[i]]; if(a[p[i]]!=a[p[i+1]]&&i!=n) cnt++; } for(int i=1;i<=n;i++) vec[rk[i]].push_back(i); sgt1.bd(1,1,n);sgt2.bd(1,1,n); for(int i=1;i<=q;i++){ cin>>l1[i]>>r1[i]>>l2[i]>>r2[i]; ask2[cnt].push_back(i); } int it1=cnt,it2=cnt;to[0]=-1e9; for(int i=cnt;i>=1;i--){ for(auto ed:ask2[i]){ while(to[it2]/2>to[i]&&it2){ for(auto ed:vec[it2]) sgt1.upd(1,1,n,ed,0); it2--; } int mxi=sgt1.qry(1,1,n,l1[ed],r1[ed]); if(to[mxi]<=to[i]){ ask1[mxi].push_back(ed); }else{ ans[ed]=to[mxi]+to[i]; } } for(auto ed:ask1[i]){ while(to[it1]>=to[i]&&it1){ for(auto ed:vec[it1]) sgt2.upd(1,1,n,ed,0); it1--; } int mxi=sgt2.qry(1,1,n,l2[ed],r2[ed]); if(to[mxi]<to[i]/2){ ask2[mxi].push_back(ed); }else{ ans[ed]=to[mxi]+to[i]; } } } for(int i=1;i<=q;i++){ cout<<ans[i]<<'\n'; }cerr<<cost<<endl; return 0; }