强行二合一啊。。。
前面直接二分最小值，二维前缀和。后面用主席树查最小值。注意要写\(nlogn\)。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
namespace solve1{
int a[201][201];
int S1[201][201][1001],S2[201][201][1001];
il int query(int S[201][201][1001],int x0,int y0,int x1,int y1,int k){return S[x1][y1][k]-S[x1][y0-1][k]-S[x0-1][y1][k]+S[x0-1][y0-1][k];}
il vd main(int n,int m,int q){
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
a[i][j]=gi();
for(int k=1;k<=a[i][j];++k)S1[i][j][k]+=a[i][j],++S2[i][j][k];
}
for(int i=1;i<=1000;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=m;++k){
S1[j][k][i]+=S1[j][k-1][i]+S1[j-1][k][i]-S1[j-1][k-1][i];
S2[j][k][i]+=S2[j][k-1][i]+S2[j-1][k][i]-S2[j-1][k-1][i];
}
int x0,y0,x1,y1,t;
int l,r,mid;
while(q--){
x0=gi(),y0=gi(),x1=gi(),y1=gi(),t=gi();
l=0,r=1000;
while(l<r){
mid=(l+r)>>1;
if(query(S1,x0,y0,x1,y1,mid+1)>=t)l=mid+1;
else r=mid;
}
if(l==0)puts("Poor QLW");
else printf("%d\n",query(S2,x0,y0,x1,y1,l+1)+(t-query(S1,x0,y0,x1,y1,l+1)+l-1)/l);
}
}
}
namespace solve2{
#define mid ((l+r)>>1)
int rt[500010],ls[10000000],rs[10000000],sum[10000000],tot[10000000],id;
il vd build(int&x,int l,int r){
x=++id;if(l==r)return;
build(ls[x],l,mid),build(rs[x],mid+1,r);
}
il vd update(int&x,int l,int r,const int&p,const int&d){
++id;ls[id]=ls[x],rs[id]=rs[x],sum[id]=sum[x],tot[id]=tot[x];x=id;
sum[x]+=d,++tot[x];if(l==r)return;
if(p<=mid)update(ls[x],l,mid,p,d);
else update(rs[x],mid+1,r,p,d);
}
il int query(int xl,int xr,int l,int r,int t,int R){
if(l==r)return R+(t+l-1)/l;
if(sum[rs[xr]]-sum[rs[xl]]>=t)return query(rs[xl],rs[xr],mid+1,r,t,R);
else return query(ls[xl],ls[xr],l,mid,t-(sum[rs[xr]]-sum[rs[xl]]),R+(tot[rs[xr]]-tot[rs[xl]]));
}
#undef mid
int S[500010],a[500010];
il vd main(int n,int q){
for(int i=1;i<=n;++i)a[i]=gi(),S[i]=S[i-1]+a[i];
build(rt[0],1,1000);
for(int i=1;i<=n;++i)rt[i]=rt[i-1],update(rt[i],1,1000,a[i],a[i]);
int L,R,t;
while(q--){
gi(),L=gi(),gi(),R=gi(),t=gi();
if(S[R]-S[L-1]<t)puts("Poor QLW");
else printf("%d\n",query(rt[L-1],rt[R],1,1000,t,0));
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("2468.in","r",stdin);
freopen("2468.out","w",stdout);
#endif
int n=gi(),m=gi(),q=gi();
if(n!=1)solve1::main(n,m,q);
else solve2::main(m,q);
return 0;
}