G - Hiring

#include <sstream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#include <string.h>
#include <assert.h>
#include <time.h>

using namespace std;

#define SZ(x) ((int)x.size())
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define clrall(name,val) memset(name,(val),sizeof(name));
#define EPS 10e-9
#define ll long long
#define ull long long unsigned
#define sf scanf
#define pf printf
#define psb(b) push_back((b))
#define ppb() pop_back()
#define oo (1<<28)
#define mp make_pair
#define mt make_tuple
#define get(a,b) get<b>(a)
#define fs first
#define sc second
#define Read freopen("in.txt","r",stdin)
#define Write freopen("out.txt","w",stdout)
#define __ std::ios_base::sync_with_stdio (false)

ll MulModL(ll B,ll P,ll M) {    ll R=0; while(P>0)      { if((P&1ll)==1) { R=(R+B); if(R>=M) R-=M; } P>>=1ll; B=(B+B); if(B>=M) B-=M; } return R; }

ll MulModD(ll B, ll P,ll M) {   ll I=((long double)B*(long double)P/(long double)M);    ll R=B*P-M*I; R=(R%M+M)%M;  return R; }

ll BigMod(ll B,ll P,ll M) {     ll R=1; while(P>0)      { if(P%2==1) { R=(R*B)%M; } P/=2; B=(B*B)%M; } return R; } /// (B^P)%M

template<class T1> void deb(T1 e1){cout<<e1<<"\n";}
template<class T1,class T2> void deb(T1 e1,T2 e2){cout<<e1<<" "<<e2<<"\n";}
template<class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3){cout<<e1<<" "<<e2<<" "<<e3<<"\n";}
template<class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<"\n";}
template<class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<"\n";}
template<class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<"\n";}
template<class T1,class T2,class T3,class T4,class T5,class T6,class T7> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6,T7 e7){cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<" "<<e7<<"\n";}

//int dx[]= {-1,-1,0,0,1,1};
//int dy[]= {-1,0,-1,1,0,1};
//int dx[]= {0,0,1,-1};/*4 side move*/
//int dy[]= {-1,1,0,0};/*4 side move*/
//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
//int dx[]={1,1,2,2,-1,-1,-2,-2};/*night move*/
//int dy[]={2,-2,1,-1,2,-2,1,-1};/*night move*/

const int MAX = 200700;
const int MAXD = 1e6+7;
vector<int> idx[MAXD+7];
pair<ll,ll> tree[MAX*4+10];
ll dur[MAX];
pair<pair<ll,ll>,int> Query[MAX];
int ans[MAX];

#define mson int mid=(l+r)>>1,nidx=(idx<<1)

void build(int idx,int l,int r)
{
    if(l==r)
    {
        tree[idx].fs=dur[l];
        tree[idx].sc=1;
        return ;
    }
    mson;
    build(nidx,l,mid);
    build(nidx+1,mid+1,r);
    tree[idx].fs=tree[nidx].fs+tree[nidx+1].fs;
    tree[idx].sc=tree[nidx].sc+tree[nidx+1].sc;
    return ;
}

void update(int idx,int l,int r,int k)
{
    if(l==r)
    {
        tree[idx].fs=0;
        tree[idx].sc=0;
        return ;
    }
    mson;
    if(k<=mid) update(nidx,l,mid,k);
    else update(nidx+1,mid+1,r,k);
    tree[idx].fs=tree[nidx].fs+tree[nidx+1].fs;
    tree[idx].sc=tree[nidx].sc+tree[nidx+1].sc;
    return ;
}
int query1(int idx,int l,int r,ll d,ll p)
{
    if(l==r) return l;
    mson;
    if(tree[nidx].fs-(d*tree[nidx].sc)>=p)
        return query1(nidx,l,mid,d,p);
    else
        return query1(nidx+1,mid+1,r,d,p-(tree[nidx].fs-(d*tree[nidx].sc)));
    return 0;
}

int query(int idx,int l,int r,ll d,ll p)
{
    if(tree[idx].fs-(d*tree[idx].sc)<p) return 0;
    return query1(idx,l,r,d,p);
}


int main()
{


    int n,m;
    sf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        sf("%lld",&dur[i]);
        idx[dur[i]].psb(i);
    }

    for(int i=0;i<n;i++)
    {
        sf("%lld %lld",&Query[i].fs.fs,&Query[i].fs.sc);
        Query[i].sc=i;
    }

    sort(Query,Query+n);

    build(1,1,m);

    int cur=0;

    for(int i=0;i<MAXD;i++)
    {
        int k=SZ(idx[i]);
        for(int j=0;j<k;j++)
        {
            update(1,1,m,idx[i][j]);
        }
        while(cur<n && Query[cur].fs.fs==(ll)i){
            ans[Query[cur].sc]=query(1,1,m,i,Query[cur].fs.sc);
            cur++;
        }
    }
    for(int i=0;i<n;i++)
    {
        pf("%d%c",ans[i]," \n"[i==n-1]);
    }

    return 0;
}


/**
5 6
9 1 3 4 6
2 16
3 7
1 15
4 10
9 1
0 23
*/
/**
10 10
54 6 65 1 54 6 3 5 9 8
10 5
5 16
3 56
98 21
65 14
24 65
7 88
69 15
3 3
*/
/**
1 62
82 86 17 55 37 35 29 98 75 21 14 60 58 43 71 22 94 74 39 63 50 48 95 93 59 42 51 37 89 12 56 93 25 69 51 13 53 21 80 16 80 61 74 73 59 47 41 40 62 79 21 71 32 46 37 13 44 10 94 18 93 63
10 1574
*/