#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    int n,q;
    cin>>n>>q;
    ll ans=0;
    if(n==1){
        while(q--){
            char c;cin>>c;
            if(c=='!')cout<<"0\n";
            else if(c=='?'){
                int x;cin>>x;
                cout<<"1 1\n";
            }
            else {
                int x;cin>>x;
            }
        }
        return;
    }
    vector<int> x(n+1),y(n+1);
    vector<int> up(n+1),down(n+1),left(n+1),right(n+1);
    int lu=0,ld=0,ru=0,rd=0;
    int l1=1,l2=n,t1=1,t2=n;//actually bound
    int x1=1,x2=n,y1=1,y2=n;//virtual bound
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        if(x[i]==1&&y[i]==1)lu++;
        else if(x[i]==1&&y[i]==n)ru++;
        else if(x[i]==n&&y[i]==1)ld++;
        else if(x[i]==n&&y[i]==n)rd++;
        else if(x[i]==1)up[y[i]]++;
        else if(x[i]==n)down[y[i]]++;
        else if(y[i]==1)left[x[i]]++;
        else if(y[i]==n)right[x[i]]++;
    }
    auto actual_point = [&](int x,int y){
        return make_pair(x-x1+l1,y-y1+t1);
    };
    while(q--){
        char c;
        if(c=='!'){cout<<ans<<"\n";continue;}
        if(c=='?'){
            int i;cin>>i;
            int ax,ay;
            if(x[i]<=x1&&y[i]<=y1)tie(ax,ay)=actual_point(x1,y1);
            else if(x[i]<=x1&&y[i]>=y2)tie(ax,ay)=actual_point(x1,y2);
            else if(x[i]>=x2&&y[i]<=y1)tie(ax,ay)=actual_point(x2,y1);
            else if(x[i]>=x2&&y[i]>=y2)tie(ax,ay)=actual_point(x2,y2);
            else if(x[i]<=x1)tie(ax,ay)=actual_point(x1,y[i]);
            else if(x[i]>=x2)tie(ax,ay)=actual_point(x2,y[i]);
            else if(y[i]<=y1)tie(ax,ay)=actual_point(x[i],y1);
            else if(y[i]<=y2)tie(ax,ay)=actual_point(x[i],y2);
            else tie(ax,ay)=actual_point(x[i],y[i]);
            cout<<ax<<" "<<ay<<"\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)solve();
    return 0;
}