#include <bits/stdc++.h>

using i64 = long long;

struct Point {
    i64 x;
    i64 y;
    Point(i64 x_ = 0, i64 y_ = 0) : x(x_), y(y_) {}
    
    i64 operator()(int v) const {
        return x * v + y;
    }
};

Point operator-(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}

i64 cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

bool operator<(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

constexpr int N = 4 * 50000;

std::vector<Point> hull[N];
int cur[N];

constexpr i64 inf = 4E18;

void add(int p, int l, int r, int x, int y, const Point &v) {
    if (l >= y || r <= x) {
        return;
    }
    if (l >= x && r <= y) {
        auto &h = hull[p];
        while (h.size() > 1 && cross(h.back() - h[h.size() - 2], v - h.back()) <= 0) {
            h.pop_back();
        }
        h.push_back(v);
        return;
    }
    int m = (l + r) / 2;
    add(2 * p, l, m, x, y, v);
    add(2 * p + 1, m, r, x, y, v);
}

i64 query(int p, int l, int r, int i, int x) {
    i64 res = inf;
    if (!hull[p].empty()) {
        auto &h = hull[p];
        int &k = cur[p];
        while (k > 0 && h[k](x) > h[k - 1](x)) {
            k--;
        }
        res = h[k](x);
    }
    if (r - l == 1) {
        return res;
    }
    int m = (l + r) / 2;
    if (i < m) {
        res = std::min(res, query(2 * p, l, m, i, x));
    } else {
        res = std::min(res, query(2 * p + 1, m, r, i, x));
    }
    return res;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    
    for (int i = 0; i < 4 * q; i++) {
        hull[i].clear();
    }
    
    std::multiset<std::array<int, 3>> S;
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        S.insert({x, y, 0});
    }
    std::vector<std::array<int, 3>> qry;
    qry.reserve(q);
    std::vector<std::tuple<Point, int, int>> pts;
    pts.reserve(n + q);
    for (int i = 0; i < q; i++) {
        int o, x, y;
        std::cin >> o >> x >> y;
        if (o == 0) {
            qry.push_back({x, y, i});
        } else if (o == 1) {
            S.insert({x, y, i});
        } else {
            auto it = S.lower_bound({x, y, 0});
            pts.emplace_back(Point(x, y), (*it)[2], i);
            S.erase(it);
        }
    }
    for (auto [x, y, i] : S) {
        pts.emplace_back(Point(x, y), i, q);
    }
    std::sort(pts.begin(), pts.end());
    for (auto [p, l, r] : pts) {
        add(1, 0, q, l, r, p);
    }
    
    int m = qry.size();
    while (true) {
        bool ok = true;
        std::vector<std::array<int, 2>> qs;
        qs.reserve(m);
        std::vector<i64> val(m);
        for (int k = 0; k < m; k++) {
            auto [L, R, i] = qry[k];
            if (L == R) {
                continue;
            }
            ok = false;
            int x = L + (R - L) / 2;
            qs.push_back({x, k});
            qs.push_back({x + 1, k});
        }
        if (ok) {
            for (int k = 0; k < m; k++) {
                auto [L, R, i] = qry[k];
                qs.push_back({L, k});
            }
        }
        std::sort(qs.begin(), qs.end());
        for (int i = 0; i < 4 * q; i++) {
            cur[i] = hull[i].size() - 1;
        }
        for (auto [x, k] : qs) {
            auto &[L, R, i] = qry[k];
            int nx = L + (R - L) / 2;
            if (x == nx) {
                val[k] = query(1, 0, q, i, x);
            } else {
                if (query(1, 0, q, i, x) > val[k]) {
                    L = x;
                } else {
                    R = x - 1;
                }
            }
        }
        if (ok) {
            for (auto x : val) {
                std::cout << x << "\n";
            }
            break;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}