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

int h, w, q;
ll a[25][25];
vector<pair<int, int>> B;

inline bool is_adj(int r1, int c1, int r2, int c2) {
    if (r1 == r2 && c1 == c2) return false;
    if (r1 == r2 || c1 == c2) return true;
    if (abs(r1 - r2) == abs(c1 - c2)) return true;
    return false;
}

void solve() {
    if (!(cin >> h >> w)) return;
    int n = h * w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < h; i++) {
        if (i % 2 == 0) {
            for (int j = 0; j < w; j++) B.push_back({i, j});
        } else {
            for (int j = w - 1; j >= 0; j--) B.push_back({i, j});
        }
    }

    vector<ll> basis(60, 0);
    vector<vector<int>> pivot_comb(60);
    vector<vector<int>> nullspace;

    for (int i = 0; i < n; i++) {
        ll val = a[B[i].first][B[i].second];
        vector<int> cur(n, 0);
        cur[i] = 1;

        for (int b = 59; b >= 0; b--) {
            if ((val >> b) & 1) {
                if (!basis[b]) {
                    basis[b] = val;
                    pivot_comb[b] = cur;
                    break;
                }
                val ^= basis[b];
                for (int j = 0; j < n; j++) cur[j] ^= pivot_comb[b][j];
            }
        }
        if (val == 0) {
            nullspace.push_back(cur);
        }
    }

    cin >> q;
    mt19937 rng(1337);

    while (q--) {
        ll x;
        cin >> x;

        if (x == 0) {
            cout << 3 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            cout << 1 << " " << 1 << "\n";
            cout << 1 << " " << 2 << "\n";
            continue;
        }

        ll rem = x;
        vector<int> c_base(n, 0);
        for (int b = 59; b >= 0; b--) {
            if ((rem >> b) & 1) {
                if (!basis[b]) {
                    rem = -1;
                    break;
                }
                rem ^= basis[b];
                for (int j = 0; j < n; j++) c_base[j] ^= pivot_comb[b][j];
            }
        }

        if (rem != 0) {
            cout << -1 << "\n";
            continue;
        }

        int best_len = 1e9;
        vector<pair<int, int>> best_path;

        auto eval_y = [&](const vector<int>& c_arr) {
            int sum_c = 0;
            for (int v : c_arr) sum_c ^= v;

            int extra = -1;
            vector<int> mod_c = c_arr;
            if (sum_c != (n % 2)) {
                extra = n - 2;
                mod_c[n - 2] ^= 1;
            }

            vector<int> y(n - 1);
            y[0] = mod_c[0] ^ 1;
            for (int i = 1; i < n - 1; i++) {
                y[i] = mod_c[i] ^ 1 ^ y[i - 1];
            }

            int w_cnt = 0;
            for (int v : y) w_cnt += v;
            int limit = (extra == -1) ? (n / 2) : ((n - 1) / 2);

            if (w_cnt <= limit) {
                vector<pair<int, int>> path;
                path.push_back(B[0]);
                for (int i = 0; i < n - 1; i++) {
                    if (y[i] == 0) {
                        path.push_back(B[i + 1]);
                    } else {
                        path.push_back(B[i + 1]);
                        path.push_back(B[i]);
                        path.push_back(B[i + 1]);
                    }
                }
                if (extra != -1) path.push_back(B[extra]);

                if ((int)path.size() - 1 < best_len) {
                    best_len = path.size() - 1;
                    best_path = path;
                }
            }
        };

        auto get_u = [&](int r, int v) {
            return make_pair(B[r].first, B[v].second);
        };

        auto eval_star = [&](const vector<int>& c_arr) {
            int ones = 0;
            vector<int> c_list;
            for (int i = 0; i < n; i++) {
                if (c_arr[i]) {
                    ones++;
                    c_list.push_back(i);
                }
            }

            if (ones == 0) {
                vector<pair<int, int>> p = {B[0], B[1], B[0], B[1]};
                if ((int)p.size() - 1 < best_len) {
                    best_len = p.size() - 1;
                    best_path = p;
                }
                return;
            }

            if (ones % 2 != 0) {
                for (int r : c_list) {
                    vector<pair<int, int>> path = {B[r]};
                    for (int v : c_list) {
                        if (v == r) continue;
                        if (is_adj(B[r].first, B[r].second, B[v].first, B[v].second)) {
                            path.push_back(B[v]);
                            path.push_back(B[r]);
                        } else {
                            auto u = get_u(r, v);
                            path.push_back(u);
                            path.push_back(B[v]);
                            path.push_back(u);
                            path.push_back(B[r]);
                        }
                    }
                    if ((int)path.size() - 1 < best_len) {
                        best_len = path.size() - 1;
                        best_path = path;
                    }
                }
            } else {
                for (int r : c_list) {
                    for (int e : c_list) {
                        if (r == e) continue;
                        vector<pair<int, int>> path = {B[r]};
                        for (int v : c_list) {
                            if (v == r || v == e) continue;
                            if (is_adj(B[r].first, B[r].second, B[v].first, B[v].second)) {
                                path.push_back(B[v]);
                                path.push_back(B[r]);
                            } else {
                                auto u = get_u(r, v);
                                path.push_back(u);
                                path.push_back(B[v]);
                                path.push_back(u);
                                path.push_back(B[r]);
                            }
                        }
                        if (is_adj(B[r].first, B[r].second, B[e].first, B[e].second)) {
                            path.push_back(B[e]);
                        } else {
                            auto u = get_u(r, e);
                            path.push_back(u);
                            path.push_back(B[e]);
                            path.push_back(u);
                        }
                        if ((int)path.size() - 1 < best_len) {
                            best_len = path.size() - 1;
                            best_path = path;
                        }
                    }
                }
            }
        };

        vector<int> c_cur = c_base;
        eval_y(c_cur);
        
        for (int iter = 0; iter < 2500; iter++) {
            if (best_len <= 2 * n - 1) break;
            c_cur = c_base;
            for (auto& nv : nullspace) {
                if (rng() % 2) {
                    for (int i = 0; i < n; i++) c_cur[i] ^= nv[i];
                }
            }
            eval_y(c_cur);
        }

        if (best_len > 2 * n - 1) {
            int max_iters = min(2500, 10000000 / (n * n * n + 1));
            if (max_iters == 0) max_iters = 1;
            c_cur = c_base;
            eval_star(c_cur);
            for (int iter = 0; iter < max_iters; iter++) {
                if (best_len <= 2 * n - 1) break;
                c_cur = c_base;
                for (auto& nv : nullspace) {
                    if (rng() % 2) {
                        for (int i = 0; i < n; i++) c_cur[i] ^= nv[i];
                    }
                }
                eval_star(c_cur);
            }
        }

        if (best_len > 2 * n - 1) {
            cout << -1 << "\n";
        } else {
            cout << best_len << "\n";
            for (auto& p : best_path) {
                cout << p.first + 1 << " " << p.second + 1 << "\n";
            }
        }
    }
}

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