#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e4+5;

ll c,t,n,k;
ll e[N][N];
ll ee[N];

int main()
{
    freopen ("traverse.in", "r", stdin);
    freopen ("traverse.out", "w", stdout);

    cin >> c >> t;
    while (t--)
    {
        cin >> n >> k;
        for (ll i = 1; i <= n; i++)
        {
            ll u,v;
            cin >> u >> v;
            e[u][v] = 1;
        }for (ll i = 1; i <= k; i++) cin >> ee[i];
        ll a = rand();
        if (c>=1&&c<=3) cout << a%6 << endl;
        else if (c>=4&&c<=10) cout << a%100001 << endl;
        else if (c>=11&&c<=12) cout << a%501 << endl;
        else if (c>=13&&c<=14) cout << a%101 << endl;
        else if (c==15) cout << a%501 << endl;
        else if (c>=22&&c<=23) cout << a%20001 << endl;
        else if (c>=24&&c<=25) cout << a%100001 << endl;
    }


    fclose (stdin);
    fclose (stdout);
    return 0;
}