This is an editorial for an \(O(N \sqrt N + Q \sqrt N)\) solution.

First, we coordinate-compress all values \(A_i\) together with every value \(x\) appearing in update operations. After that, we may assume that the value range of \(A_i\) is \(O(N)\).

Next, we divide the sequence \(A\) into \(O(\sqrt N)\) blocks, and also divide the value range into \(O(\sqrt N)\) blocks. We then maintain the following information:

• \(s_{i, j}\): the sum of all numbers in the first \(i\) sequence blocks whose values belong to the \(j\)-th value block. (Note that the sum is taken over the original values before coordinate compression.)
• \(c_{i, j}\): the sum of all numbers in the first \(i\) sequence blocks whose compressed value is \(j\).
• \(cs_{i, j}\): the number of elements in the first \(i\) sequence blocks whose values belong to the \(j\)-th value block.
• \(cc_{i, j}\): the number of elements in the first \(i\) sequence blocks whose compressed value is \(j\).

After coordinate-compressing the sequence \(A\), all four pieces of information can be computed in \(O(N \sqrt N)\) time.

Now consider an update operation \(A_c := x\). We first remove the contribution of the original value \(A_c\), and then add the contribution of \(x\). Suppose that position \(c\) belongs to the \(b\)-th sequence block. Then only the information corresponding to the \(b\)-th sequence block and all subsequent sequence blocks needs to be updated. Therefore, each update takes \(O(\sqrt N)\) time.

Next, consider a query \((l, r, k)\).

---

If \(l\) and \(r\) belong to the same sequence block, then we can compute the following four arrays in \(O(r-l)\) time:

• \(ts_{j}\): the sum of all numbers in the interval \([l, r]\) whose values belong to the \(j\)-th value block.
• \(tc_{j}\): the sum of all numbers in the interval \([l, r]\) whose compressed value is \(j\).
• \(tcs_{j}\): the number of elements in the interval \([l, r]\) whose values belong to the \(j\)-th value block.
• \(tcc_{j}\): the number of elements in the interval \([l, r]\) whose compressed value is \(j\).

After obtaining the above information, we enumerate the value blocks from largest to smallest. Suppose we are currently processing the \(j\)-th value block. Meanwhile, we maintain an answer \(ans\), which is initially \(0\).

• If \(k > ts_j\), subtract \(ts_j\) from \(k\), and add \(tcs_j\) to \(ans\).

• Otherwise, enumerate every value \(p\) in the current block from largest to smallest.

  • If \(k > tc_p\), subtract \(tc_p\) from \(k\), and add \(tcc_p\) to \(ans\).
  • Otherwise, suppose the original value corresponding to \(p\) before coordinate compression is \(y\). Then we need to take \(\displaystyle{\left \lceil \frac{k}{y}\right\rceil}\) copies of \(y\), so we add \(\displaystyle{\left \lceil \frac{k}{y}\right\rceil}\) to \(ans\) and terminate.

If the sum of all numbers in the interval is less than \(k\), return \(-1\).

---

If \(l\) and \(r\) do not belong to the same sequence block, let \(R\) denote the right endpoint of the block containing \(l\), and let \(L\) denote the left endpoint of the block containing \(r\).

Then we can compute the following four arrays in \(O(\sqrt N)\) time:

• \(ts_{j}\): the sum of all numbers in the interval \([l, R] \cup [L, r]\) whose values belong to the \(j\)-th value block.
• \(tc_{j}\): the sum of all numbers in the interval \([l, R] \cup [L, r]\) whose compressed value is \(j\).
• \(tcs_{j}\): the number of elements in the interval \([l, R] \cup [L, r]\) whose values belong to the \(j\)-th value block.
• \(tcc_{j}\): the number of elements in the interval \([l, R] \cup [L, r]\) whose compressed value is \(j\).

Suppose the sequence block indices containing \(l\) and \(r\) are \(bel_l\) and \(bel_r\), respectively.

Then the sum of all numbers in \([l, r]\) whose values belong to the \(j\)-th value block is \(ts_j + s_{bel_r-1, j} - s_{bel_l, j}\). The other three pieces of information can be obtained similarly.

Finally, the procedure for computing the answer is essentially the same as in the case where \(l\) and \(r\) belong to the same block, so we omit the details here.

Therefore, each query can always be answered in \(O(\sqrt N)\) time. Overall, the problem can be solved in \(O(N \sqrt N + Q \sqrt N)\) time.

#include<bits/stdc++.h>
#define endl '\n'
#define N 200006
#define M 460
using namespace std;
constexpr int B=500;
using i64=long long;
int n,q,bn,a[N],b[N],lb[N],rb[N];
struct Ask {int c,x,l,r; i64 k;} ask[N];
i64 c[M][N],s[M][M],tc[N],ts[M];
int cc[M][N],cs[M][M],tcc[N],tcs[M];
inline int bel(int x) {return (x-1)/B+1;}
void update(int k,int x)
{
  for(int i=bel(k);i<=bel(n);i++)
  {
    c[i][a[k]]-=b[a[k]],cc[i][a[k]]--;
    s[i][bel(a[k])]-=b[a[k]],cs[i][bel(a[k])]--;
  }
  a[k]=x;
  for(int i=bel(k);i<=bel(n);i++)
  {
    c[i][a[k]]+=b[a[k]],cc[i][a[k]]++;
    s[i][bel(a[k])]+=b[a[k]],cs[i][bel(a[k])]++;
  }
}
int query(int l,int r,i64 x)
{
  if(bel(l)==bel(r))
  {
    for(int i=l;i<=r;i++)
    {
      tc[a[i]]+=b[a[i]],tcc[a[i]]++;
      ts[bel(a[i])]+=b[a[i]],tcs[bel(a[i])]++;
    }
    int ret=0,fd=0;
    for(int i=bel(bn);i&&!fd;i--)
    {
      int l=lb[i],r=rb[i];
      if(x>ts[i])x-=ts[i],ret+=tcs[i];
      else {
        for(int j=r;j>=l&&!fd;j--)
          if(x>tc[j])x-=tc[j],ret+=tcc[j];
          else ret+=(x-1)/b[j]+1,fd=1;
      }
    }
    for(int i=l;i<=r;i++)
      tc[a[i]]=tcc[a[i]]=0,ts[bel(a[i])]=tcs[bel(a[i])]=0;
    return fd?ret:-1;
  }
  int bl=bel(l),br=bel(r);
  for(int i=l;i<=bl*B;i++)
  {
    tc[a[i]]+=b[a[i]],tcc[a[i]]++;
    ts[bel(a[i])]+=b[a[i]],tcs[bel(a[i])]++;
  }
  for(int i=(br-1)*B+1;i<=r;i++)
  {
    tc[a[i]]+=b[a[i]],tcc[a[i]]++;
    ts[bel(a[i])]+=b[a[i]],tcs[bel(a[i])]++;
  }
  int ret=0,fd=0;
  for(int i=bel(bn);i&&!fd;i--)
  {
    int l=lb[i],r=rb[i];
    i64 now_s=ts[i]+s[br-1][i]-s[bl][i];
    int now_cs=tcs[i]+cs[br-1][i]-cs[bl][i];
    if(x>now_s)x-=now_s,ret+=now_cs;
    else {
      for(int j=r;j>=l&&!fd;j--)
      {
        i64 now_c=tc[j]+c[br-1][j]-c[bl][j];
        int now_cc=tcc[j]+cc[br-1][j]-cc[bl][j];
        if(x>now_c)x-=now_c,ret+=now_cc;
        else ret+=(x-1)/b[j]+1,fd=1;
      }
    }
  }
  for(int i=l;i<=bl*B;i++)
  {
    tc[a[i]]=tcc[a[i]]=0;
    ts[bel(a[i])]=tcs[bel(a[i])]=0;
  }
  for(int i=(br-1)*B+1;i<=r;i++)
  {
    tc[a[i]]=tcc[a[i]]=0;
    ts[bel(a[i])]=tcs[bel(a[i])]=0;
  }
  return fd?ret:-1;
}
main()
{
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[++bn]=a[i];
  for(int i=1;i<=q;i++)
  {
    scanf("%d%d",&ask[i].c,&ask[i].x);
    scanf("%d%d%lld",&ask[i].l,&ask[i].r,&ask[i].k);
    b[++bn]=ask[i].x;
  }
  sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
  for(int l=1,r;l<=bn;l=r+1)
    r=min(l+B-1,bn),lb[bel(l)]=l,rb[bel(r)]=r;
  for(int i=1;i<=n;i++)
  {
    a[i]=lower_bound(b+1,b+1+bn,a[i])-b;
    c[bel(i)][a[i]]+=b[a[i]],cc[bel(i)][a[i]]++;
    s[bel(i)][bel(a[i])]+=b[a[i]],cs[bel(i)][bel(a[i])]++;
  }
  for(int i=1;i<=bel(n);i++)
  {
    for(int j=1;j<=bn;j++)
      c[i][j]+=c[i-1][j],cc[i][j]+=cc[i-1][j];
    for(int j=1;j<=bel(bn);j++)
      s[i][j]+=s[i-1][j],cs[i][j]+=cs[i-1][j];
  }
  for(int i=1;i<=q;i++)
  {
    int c=ask[i].c,x=ask[i].x,l=ask[i].l,r=ask[i].r;
    i64 k=ask[i].k;
    x=lower_bound(b+1,b+1+bn,x)-b,update(c,x);
    printf("%d\n",query(l,r,k));
  }
  return 0;
}