#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int N;
struct pstslog{
   ll suma=0,kol=0;
   int d1=0,d2=0;
}pst[30000000];
int pss=0;
int novi(){
   pss++;
   pst[pss].suma=0;
   pst[pss].kol=0;
   pst[pss].d1=pst[pss].d2=0;
   return pss;
}
int pvrem=0,root[200005];
void psupdate(int gde,int upd,int lc,int dc,int stavi){

   if(lc==dc){
      pst[gde].suma+=stavi;
      pst[gde].kol++;
      return;
   }
   int sred=(lc+dc)/2;
   if(upd<=sred){
      int koji=novi();
      pst[koji]=pst[pst[gde].d1];
      pst[gde].d1=koji;
      psupdate(koji,upd,lc,sred,stavi);
   }
   else{
      int koji=novi();
      pst[koji]=pst[pst[gde].d2];
      pst[gde].d2=koji;
      psupdate(koji,upd,sred+1,dc,stavi);
   }
   pst[gde].suma=pst[pst[gde].d1].suma+pst[pst[gde].d2].suma;
   pst[gde].kol=pst[pst[gde].d1].kol+pst[pst[gde].d2].kol;
   /*
   cout<<gde<<" "<<lc<<" "<<dc<<" "<<upd<<" "<<stavi<<endl;
   cout<<pst[gde].suma<<" "<<pst[gde].kol<<endl;*/
   return;
}
void pstupdate(int koji,int stavi){
   pvrem++;
   root[pvrem]=novi();
   pst[root[pvrem]]=pst[root[pvrem-1]];
   psupdate(root[pvrem],koji,1,(1<<30),stavi);
}
ll get(int poz,int k){
   //cout<<k<<endl;
   //cout<<poz<<" "<<pst[poz].suma<<" "<<pst[poz].kol<<endl;
   if(k<=0)
      return 0;
   if(pst[poz].kol<k)
      return 1e18;
   if(pst[poz].kol==k)
      return pst[poz].suma;
   if(pst[pst[poz].d1].kol>=k)
      return get(pst[poz].d1,k);
   return pst[pst[poz].d1].suma+get(pst[poz].d2,k-pst[pst[poz].d1].kol);
}
ll suma(int gde,int k){
   if(N-gde+1<k)
      return 1e18;
   int v=N-gde+1;
   v=root[v];
   return get(v,k);
}

const int maxn=2e5+5;
ll M,suf[maxn],cena[maxn],res[maxn];
int pitaj(int idx,int s,int e){
   ll mcena=1e18;
   int ret;
   for(int i=e;i>=s;i--){
      if(N-i<idx-1)
         continue;
      ll v=0;
      v+=cena[i];
      v-=suf[i];
      v+=suma(i+1,idx-1);
      if(v<mcena){
         mcena=v;
         ret=i;
      }
   }
   res[idx]=mcena;
 //  cout<<idx<<" "<<ret<<" "<<cena[ret]<<" "<<suf[ret]<<" "<<suma(ret+1,idx-1)<<endl;
   return ret;
}
void resi(int brl,int brr,int lb,int ub){
   if(brr<brl)
      return;
   int mid=(brl+brr)/2;
   int gde=pitaj(mid,lb,ub);
   resi(brl,mid-1,gde,ub);
   resi(mid+1,brr,lb,gde);
}
void solve(){
   pst[0].suma=pst[0].kol=0;
   pst[0].d1=pst[0].d2=0;
   pss=0;

   cin>>N>>M;
   for(int i=1;i<=N;i++)
      cin>>cena[i];
   int a,b;
   while(M--){
      cin>>b>>a;
      suf[b]+=a;
   }
   for(int i=N-1;i>=1;i--)
      suf[i]+=suf[i+1];

   for(int i=N;i>=1;i--)
      pstupdate(cena[i],cena[i]);

   //cout<<suma(5,5)<<endl;
   //return;
   /*for(int i=1;i<=N;i++)
   for(int j=1;j<=N;j++){
      cout<<i<<" "<<j<<" "<<suma(i,j)<<endl;
   }
   return;*/
   resi(1,N,1,N);

   for(int i=1;i<=N;i++)
      cout<<res[i]<<" ";
   cout<<"\n";
}
void reset(){
   for(int i=1;i<=N;i++){
      suf[i]=0;
      cena[i]=0;
      res[i]=0;
   }
   pvrem=0;
   pss=0;
}
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int T;
   cin>>T;
   while(T--){
      solve();
      reset();
   }
}