#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define rep(i,l,r) for(ll i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(ll i(r),i##end(l);i>=i##end;--i)
#define dbg(x) cerr<<#x<<" "<<x<<'\n';
#define ll long long
#define gc getchar
#define pc putchar
using namespace std;
namespace WrongIO
{
	#define Ts template<typename Ty,typename... Ar>
	#define Tp template<typename Ty>
	Tp Ty wmax(Ty a,Ty b){return a>=b? a:b;}
	Tp Ty wmin(Ty a,Ty b){return a<=b? a:b;}
	Tp void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp void write(Ty x){short OI_USE[150],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts void read(Ty &x,Ar &...y) {read(x),read(y...);}
    Tp void writeln(Ty x) {write(x),pc('\n');}
    Tp void writesp(Ty x) {write(x),pc(' ');} 
    #undef Ts
	#undef Tp
} using namespace WrongIO;
const ll N=5e5+50;
ll n,m;
vector<ll> vt[N*4],qs[N];
ll st[N*4],vis[N],vks[N*4],wz[N];
void update(ll pos)
{
	st[pos]=0;
	if(pos*2<=4*n) st[pos]+=st[pos<<1];
	if(pos*2+1<=4*n) st[pos]+=st[pos<<1|1];
}
void cle(ll L,ll R,ll pos)
{
	vt[pos].clear();
	if(L==R) return vks[pos]=1,wz[L]=pos,st[pos]=1,void();
	ll mid=(L+R)/2;
	cle(L,mid,pos<<1);
	cle(mid+1,R,pos<<1|1);
	update(pos); vks[pos]=(st[pos]==1? 1:2);
}
void dt(ll L,ll R,ll EL,ll ER,ll vlx,ll pos)
{
	if(L>ER||R<EL) return;
	if(EL<=L&&R<=ER) return qs[vlx].push_back(pos),vt[pos].push_back(vlx),void();
	ll mid=(L+R)/2;
	dt(L,mid,EL,ER,vlx,pos<<1);
	dt(mid+1,R,EL,ER,vlx,pos<<1|1);
}
ll la;
void solve()
{
	read(n,m); la=0;
	rep(i,0,max(n,m)) qs[i].clear(),vis[i]=0,wz[i]=0;
	rep(i,0,4*n) st[i]=0,vks[i]=0;
	cle(1,n,1);
	rep(i,1,m)
	{
		ll u,v; read(u,v); u++; v++;
		if(u-v==0) la+=i*i,vis[i]=1; 
		dt(1,n,u,v,i,1);
	}
	writesp(la);
	rep(i,1,n)
	{
		ll pa; read(pa);
		pa=(pa+la)%n; pa++;
		ll pos=wz[pa]; st[pos]=0;
		while(pos)
		{
			if(pos!=wz[pa]) update(pos);
			if(vks[pos]==2&&st[pos]==1)
			{
				vks[pos]=1;
				for(ll id:vt[pos])
				{
					if(vis[id]==1) continue;
					ll ok=0; 
					for(ll ck:qs[id])
					ok+=st[ck];
					if(ok==1) vis[id]=1,la+=id*id;
				}
				
			}
			if(vks[pos]==1&&st[pos]==0)
			{
				vks[pos]=0;
				for(ll id:vt[pos])
				{
					
					ll ok=0; 
					for(ll ck:qs[id]) ok+=st[ck];
					if(ok==1&&vis[id]==0) vis[id]=1,la+=id*id;
					if(ok==0&&vis[id]==1) vis[id]=0,la-=id*id;
				}
			}
			pos/=2;
		}
		writesp(la);
	}
	pc('\n');
}
ll T;
int main()
{
	//freopen("a.out","w",stdout);
	//fo("t3");
	read(T);
	while(T--) solve();
}