#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define mk make_pair
#define SZ(x) (int((x).size()))

typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 2e5 + 5;

int n, m, c[MAXN], v[MAXN];
int last[MAXN];
set<int> pos[MAXN];

int Max[MAXN << 2];

void upd(int x, int l, int r, int pos, int val) {
    if(l == r) {
        Max[x] = val;
        return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid) upd(x << 1, l, mid, pos, val);
    else upd(x << 1 | 1, mid + 1, r, pos, val);
    Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
}

int get(int x, int l, int r, int ql, int val) {
    if(Max[x] <= val) return r;
    if(l == r) return l - 1;
    int mid = l + r >> 1;
    if(ql >= mid) return get(x << 1 | 1, mid + 1, r, ql, val);
    else {
        int t = get(x << 1, l, mid, ql, val);
        if(t == mid) return get(x << 1 | 1, mid + 1, r, ql, val);
        else return t;
    }
}

int rt[MAXN], tot, ls[MAXN * 100], rs[MAXN * 100], Maxx[MAXN * 100]; 
ll sum[MAXN * 100];

ll askSum(int x, int l, int r, int ql, int qr) {
    if(!x) return x;
    if(ql <= l && r <= qr) return sum[x];
    int mid = l + r >> 1;
    if(qr <= mid) return askSum(ls[x], l, mid, ql, qr);
    else if(ql > mid) return askSum(rs[x], mid + 1, r, ql, qr);
    else return askSum(ls[x], l, mid, ql, qr) + askSum(rs[x], mid + 1, r, ql, qr);
}

int askMax(int x, int l, int r, int ql, int qr) {
    if(!x) return x;
    if(ql <= l && r <= qr) return Maxx[x];
    int mid = l + r >> 1;
    if(qr <= mid) return askMax(ls[x], l, mid, ql, qr);
    else if(ql > mid) return askMax(rs[x], mid + 1, r, ql, qr);
    else return max(askMax(ls[x], l, mid, ql, qr), askMax(rs[x], mid + 1, r, ql, qr));
}

void ins(int &x, int l, int r, int p, int v) {
    if(l == r) {
        sum[x] += v, Maxx[x] += v;
        return ;
    }
    int mid = l + r >> 1;
    if(p <= mid) ins(ls[x], l, mid, p, v);
    else ins(rs[x], mid + 1, r, p, v);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    Maxx[x] = max(Maxx[ls[x]], Maxx[rs[x]]);
}

void calc(int l, int k) {
    set<int> a; a.clear();
    int now = l, r = l;
    for(int i = 0; i <= k; i++) {
        int p = get(1, 1, n, now, l);
        now = p + 1, r = p;
        a.insert(c[p]);
        if(r == n) break;
    }
    cout << l << ' ' << k << ' ' << r << '\n';
    ll ans = askSum(rt[0], 1, n, l, r);
    for(auto o : a) {
        ans -= askSum(rt[o], 1, n, l, r);
        ans += askMax(rt[o], 1, n, l, r);
    }
    cout << ans << '\n';
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) pos[i].insert(0);
    for(int i = 1; i <= n; i++) {
        cin >> c[i] >> v[i];
        last[i] = *pos[c[i]].rbegin();
        pos[c[i]].insert(i), upd(1, 1, n, i, last[i]);
        ins(rt[0], 1, n, i, v[i]);
        ins(rt[c[i]], 1, n, i, v[i]);
    }
    for(int i = 1; i <= m; i++) {
        int opt;
        cin >> opt;
        if(opt == 1) {
            int x, co, vo;
            cin >> x >> co >> vo;
            {
                pos[c[x]].erase(x);
                auto o = pos[c[x]].upper_bound(x);
                if(o != pos[c[x]].end()) {
                    int t = *o;
                    last[t] = *--o, upd(1, 1, n, t, last[t]);
                } 
            }
            ins(rt[0], 1, n, x, -v[x]);
            ins(rt[c[x]], 1, n, x, -v[x]);
            c[x] = co, v[x] = vo;
            ins(rt[0], 1, n, x, v[x]);
            ins(rt[c[x]], 1, n, x, v[x]);
            {
                auto o = pos[c[x]].upper_bound(x);
                if(o != pos[c[x]].end()) {
                    int t = *o;
                    last[t] = x, upd(1, 1, n, t, last[t]);
                } 
                last[x] = *--o, upd(1, 1, n, x, last[x]);
                pos[c[x]].insert(x);
            }
        } else {
            int s, k;
            cin >> s >> k;
            calc(s, k);
        }
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}