#include<bits/stdc++.h>
#define int long long
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
const int N=5e5+5;
int T,n,m,x,l[N],r[N];
long long ans;
vector<pair<int,int> > a[N];
set<int> s;
struct node{
	int l,r;
	vector<int> g;
	vector<long long> s;
}t[N<<2];
void push_up(int k){
	int i=0,j=0;
	while(i<t[ls].g.size()&&j<t[rs].g.size()){
		if(t[ls].g[i]<t[rs].g[j]) t[k].g.push_back(t[ls].g[i]),t[k].s.push_back(t[ls].s[i++]);
		else t[k].g.push_back(t[rs].g[j]),t[k].s.push_back(t[rs].s[j++]);
	}
	while(i<t[ls].g.size()) t[k].g.push_back(t[ls].g[i]),t[k].s.push_back(t[ls].s[i++]);
	while(j<t[rs].g.size()) t[k].g.push_back(t[rs].g[j]),t[k].s.push_back(t[rs].s[j++]);
}
void build(int k,int l,int r){
	t[k].l=l;
	t[k].r=r;
	t[k].g.clear();
	t[k].s.clear();
	if(l==r){
		for(int i=0;i<a[l].size();i++) t[k].g.push_back(a[l][i].first),t[k].s.push_back(a[l][i].second*a[l][i].second);
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(k);
}
void dfs(int k){
	for(int i=1;i<t[k].s.size();i++) t[k].s[i]+=t[k].s[i-1];
	if(t[k].l==t[k].r) return;
	dfs(ls);
	dfs(rs);
}
long long query(int k,int l1,int l2,int r1,int r2){
	if(l1>l2||r1>r2||l2<t[k].l||t[k].r<l1||t[k].g.empty()) return 0;
	if(l1<=t[k].l&&t[k].r<=l2){
		int l=lower_bound(t[k].g.begin(),t[k].g.end(),r1)-t[k].g.begin(),r=upper_bound(t[k].g.begin(),t[k].g.end(),r2)-t[k].g.begin()-1;
		if(r<0) return 0;
		if(l) return t[k].s[r]-t[k].s[l-1];
		return t[k].s[r];
	}
	return query(ls,l1,l2,r1,r2)+query(rs,l1,l2,r1,r2);
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		for(int i=0;i<n;i++) a[i].clear();
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&l[i],&r[i]);
			a[l[i]].push_back(make_pair(r[i],i));
		}
		for(int i=0;i<n;i++) sort(a[i].begin(),a[i].end());
		build(1,0,n-1);
		dfs(1);
		ans=0;
		for(int i=1;i<=m;i++) if(l[i]==r[i]) ans+=i*i;
		s.clear();
		for(int i=-1;i<=n;i++) s.insert(i);
		printf("%lld ",ans);
		for(int i=0;i<n;i++){
			scanf("%lld",&x);
			x=(x+ans)%n;
			auto it=s.find(x);
			ans-=query(1,(*prev(it,1))+1,x,x,(*next(it,1))-1);
			if((*prev(it,1))!=-1) ans+=query(1,(*prev(it,2))+1,*prev(it,1),x,(*next(it,1)-1));
			if((*next(it,1))!=n) ans+=query(1,(*prev(it,1))+1,x,*next(it,1),(*next(it,2)-1));
			s.erase(x);
			printf("%lld ",ans);
		}
		printf("\n");
	}
	return 0;
}