#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 5e5 + 5;
int qwq,n,m,l,r,k;
vector<pair<int,int> > tree[N];
set<int> st;
map<pair<int,int>,int> mp;
vector<int> sum[N];
#define lowbit(x) ((x) & (-x))
void update(int l,int r,int pos){
	for(int i = l;i <= n;i += lowbit(i))tree[i].push_back({r,pos * pos});
}
int query(int l,int r1,int r2){
	if(r1 > r2)return 0;
	int ans = 0;
	for(int i = l;i >= 1;i -= lowbit(i)){
		int posl = lower_bound(tree[i].begin(),tree[i].end(),make_pair(r1,0ll)) - tree[i].begin() - 1;
		int vall = (~posl ? sum[i][posl] : 0ll);
		int posr = upper_bound(tree[i].begin(),tree[i].end(),make_pair(r2,1145141919810ll)) - tree[i].begin() - 1;
		int valr = (~posr ? sum[i][posr] : 0ll);
		ans += valr - vall;
	}
//	cout << " " << l << " " << r1 << " " << r2 << " " << ans << endl;
	return ans;
}
int query(int l1,int l2,int r1,int r2){
	if(l1 > l2)return 0;
	return query(l2,r1,r2) - query(l1 - 1,r1,r2);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> qwq;
	while(qwq--){
		cin >> n >> m;
		st.clear(),mp.clear();
		for(int i = 1;i <= n;i++)tree[i].clear(),sum[i].clear();
		int lst = 0;
		for(int i = 1;i <= m;i++)cin >> l >> r,l++,r++,update(l,r,i),lst += (l == r) * i * i,mp[{l,r}] += i * i;
		for(int i = 1;i <= n;i++){
			st.insert(i);
			sort(tree[i].begin(),tree[i].end());
			if(tree[i].size()){
				sum[i].push_back(tree[i][0].second);
				for(int j = 1;j < tree[i].size();j++)sum[i].push_back(sum[i].back() + tree[i][j].second);
			}
		}
		cout << lst << " ";
		for(int i = 1;i <= n;i++){
			cin >> k;
			k = (k + lst) % n + 1;
			if(st.find(k) == st.end())return 0;
//			assert(st.find(k) != st.end());
			auto it = st.find(k);
			int x = (*it);
			int l = 0;
			if(it == st.begin())l = 1;
			else{
				l = *prev(it,1) + 1;
			}
			int r = 0;
			if(next(it,1) == st.end())r = n;
			else{
				r = *next(it,1) - 1;
				int r2 = 0;
				if(next(it,2) == st.end())r2 = n;
				else r2 = *next(it,2) - 1;
//				cout << "(" << l << " " << x << " " << r + 1 << " " << r2 << ")" << query(l,x,r + 1,r2) << " ";
				lst += query(l,x,r + 1,r2);
			}
			if(l != 1){
				int l2 = 0;
				if(prev(it,1) == st.begin())l2 = 1;
				else l2 = *prev(it,2) + 1;
				lst += query(l2,l - 1,x,r);
			}
			lst -= query(l,x,x,r);
//			cout << "(" << l << " " << x << " " << r << ")" << query(l,x,x,r) << " " << lst << endl;
			st.erase(it);
			cout << lst << " ";
		}
		cout << endl;
	}
}