#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<array>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 5e5 + 5;
vector<pair<int, int> > s[maxn * 4];
int x[maxn], y[maxn];

void insert(int u, int l, int r, int id){
    s[u].push_back({y[id], id});
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x[id] <= mid) insert(2 * u, l, mid, id);
    else insert(2 * u + 1, mid + 1, r, id);
}

vector<int> p;

bool del[maxn];

void query(int u, int l, int r, int L, int R, int ll, int rr){
    if (l > R or r < L) return;
    if (l >= L and r <= R){
        while(!s[u].empty()){
            if (del[s[u].back().second]){
                s[u].pop_back();
            }
            else if (s[u].back().first <= rr){
                del[s[u].back().second] = true;
                p.push_back(s[u].back().second);
                s[u].pop_back();
            }
            else break;
        }
        return;
    }
    int mid = (l + r) / 2;
    query(2 * u, l, mid, L, R, ll, rr);
    query(2 * u + 1, mid + 1, r, L, R, ll, rr);
}


int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;

        for(int i = 1; i <= 4 * n; i++){
            s[i].clear();
        }

        LL ans = 0;
        vector<LL> mp(n + 1);
        for(int i = 1; i <= m; i++){
            del[i] = false;
            cin >> x[i] >> y[i];
            x[i] += 1, y[i] += 1;
            if (y[i] - x[i] + 1 == 1){
                ans += 1LL * i * i;
                mp[x[i]] += 1LL * i * i;
            }
            else{
                insert(1, 1, n, i);
            }
        }

        for(int i = 1; i <= 4 * n; i++){
            sort(s[i].begin(), s[i].end(), greater<>());
        }

        set<int> s0;
        for(int i = 0; i <= n + 1; i++) s0.insert(i);

        auto solve = [&](int x){
            if (x < 1 or x > n) return;
            auto it = s0.lower_bound(x);
            int pre = *prev(it) + 1;
            int nxt = *next(it) - 1;
            // [pre, x], [x, nxt]
            p.clear();
            query(1, 1, n, pre, x, x, nxt);
            for(auto id : p){
                ans += 1LL * id * id;
                mp[x] += 1LL * id * id;
            }
        };

        cout << ans << ' ';
        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
            x = (x + ans) % n + 1;
            ans -= mp[x];
            s0.erase(x);
            auto it = s0.lower_bound(x);
            solve(*prev(it));
            solve(*it);
            cout << ans << ' ';
        }
        cout << '\n';
    }

}