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

const int MAXN = 2e5 + 10;
int pr[MAXN], p_sz;
bool vis[MAXN];
void init() {
    for (int i = 2; i < MAXN; i++) {
        if (!vis[i]) pr[p_sz++] = i;
        for (int j = 0; j < p_sz; j++) {
            if (pr[j] * i >= MAXN) break;
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
void change(int num, set<int> &st) {
    int t = sqrt(num + 0.5);
    for (int i = 0; pr[i] <= t; i++) {
        if (num % pr[i] == 0) {
            st.insert(pr[i]);
            while (num % pr[i] == 0)
                num /= pr[i];
        }
    }
    if (num > 1) st.insert(num);
}
int T, n, m;
struct Node {
    int l, r;
    int ll, rr;
    set<int> st;
    Node(int l = 0, int r = 0, int ll = 0, int rr = 0) : l(l), r(r), ll(ll), rr(rr) {}
    void init() {
        st.clear();
        l = r = ll = rr = 0;
    }
} a[MAXN];

struct BNode {
    int num;
    int l, r;
    void init() {
        l = r = 0;
    }
} b[MAXN];
map<int, int> mp;

void fun() { // update a[].l, a[].r
    for (int i = n; i >= 1; i--) {
        int ind = i;
        while (ind < n && b[ind].l >= i) { // 需要的在起点的右边
            ind = a[ind + 1].r;
        }
        a[i].r = ind;
    }
    for (int i = 1; i <= n; i++) {
        int ind = i;
        while (ind - 1 > 0 && b[ind - 1].r <= i) {
            ind = a[ind - 1].l;
        }
        a[i].l = ind;
    }
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        a[i].init(), b[i].init();
    int tmp;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tmp);
        change(tmp, a[i].st);
        a[i].l = a[i].r = a[i].ll = a[i].rr = i;
        // printf("qweqwr ");
        // for (auto it: a[i].st)
        // 	printf("%d ", it);
        // puts("");
    }
    for (int i = 1; i < n; i++)
        scanf("%d", &b[i].num);
    mp.clear();
    for (int i = 1; i <= n; i++) {
        for (auto it : a[i].st) {
            mp[it] = i;
        }
        if (i != n) {
            if (mp.count(b[i].num))
                b[i].l = mp[b[i].num];
            else
                b[i].l = 0;
        }
    }
    mp.clear();
    for (int i = n; i >= 1; i--) {
        for (auto it : a[i].st)
            mp[it] = i;
        if (i != 1) {
            if (mp.count(b[i - 1].num))
                b[i - 1].r = mp[b[i - 1].num];
            else
                b[i - 1].r = n + 1;
        }
    }
    // for (int i = 1; i < n; i++)
    // 	printf("%d %d\n", b[i].l, b[i].r);

    fun();

    a[1].ll = a[1].l, a[1].rr = a[1].r;
    for (int i = 2; i <= n; i++) {
        if (a[i - 1].rr >= i && a[i].l <= i - 1) {
            a[i].ll = a[i - 1].ll;
            a[i].rr = a[i - 1].rr;
        } else {
            int indr = a[i].r;
            int indl = a[i - 1].ll;
            if (a[i].l >= i) indl = a[i].l;
            while (1) {
                bool flag = false;
                while (indr < n && b[indr].l >= indl) {
                    indr = a[indr + 1].r;
                    flag = true;
                }
                while (indl - 1 > 0 && b[indl - 1].r <= indr) {
                    indl = a[indl - 1].ll;
                    indr = max(indr, a[indl - 1].rr);
                    flag = true;
                }
                if (!flag) break;
            }
            a[i].ll = indl;
            a[i].rr = indr;
        }
    }
    int x, y;
    // printf("dadfad ");
    for (int i = 1; i <= n; i++)
        printf("%d %d\n", a[i].ll, a[i].rr);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        if (i == 20) printf("%d %d\n", x, y);
        // if (y >= a[x].ll && y <= a[x].rr)
        //     puts("Yes");
        // else
        //     puts("No");
    }
}

int main() {
#ifdef TanJI
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
    init();
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}