#include <fstream>
#include <iostream>
#include <queue>
#include <list>
#include <utility>
#include <algorithm>
#include <stack>

constexpr int kMaxN = 200; //number of columns
constexpr int kMaxM = 200; //number of rows
constexpr int kMaxNests = 101;

constexpr int kMarkDanger = -1;
constexpr int kEmpty = 0;

int test_type, n, m, k, g, n_nests;
int mole_x, mole_y;
int map_danger[kMaxM+1][kMaxN+1];
int map_nests[kMaxM+1][kMaxN+1]; //identified by ids
std::list<int> edges[kMaxNests+1]; //the edges of a nest with a certain id
int nests_coordinates[kMaxNests+1][2];
std::vector<int> euler_circuit;

void markDanger(int x, int y, int z) {
    map_danger[x][y] = kMarkDanger;
    if(z == 0) return;
    if(x > 1) map_danger[x-1][y] = kMarkDanger;
    if(x < m) map_danger[x+1][y] = kMarkDanger;
    if(y > 1) map_danger[x][y-1] = kMarkDanger;
    if(y < n) map_danger[x][y+1] = kMarkDanger;
    if(z == 1) return;
    if(x > 2) map_danger[x-2][y] = kMarkDanger;
    if(x < m-1) map_danger[x+2][y] = kMarkDanger;
    if(y > 2) map_danger[x][y-2] = kMarkDanger;
    if(y < n-1) map_danger[x][y+2] = kMarkDanger;
    if(x > 1 && y > 1) map_danger[x-1][y-1] = kMarkDanger;
    if(x > 1 && y < n) map_danger[x-1][y+1] = kMarkDanger;
    if(x < m && y > 1) map_danger[x+1][y-1] = kMarkDanger;
    if(x < m && y < n) map_danger[x+1][y+1] = kMarkDanger;
}

/**
    Compute the distance to the first safe nest, starting from (x, y).
    Carefull! It does modify the map_danger matrix, marking some cells with positive values.
    Carefull! IT might modify the mole_x and mole_y coordinates to indicate the mole's new position.
    @return the distance to the first safe nest, -1 if no such thing exists.
*/
int markLee(int x, int y)
{
    std::queue<std::pair<int, int> > Q;
    Q.push(std::make_pair(x, y));
    map_danger[x][y] = 1;
    while(!Q.empty()) {
        x = Q.front().first;
        y = Q.front().second;
        if(map_nests[x][y] != kEmpty) {
            mole_x = x;
            mole_y = y;
            return map_danger[x][y]-1;
        }
        Q.pop();
        if(x > 1 && map_danger[x-1][y] == kEmpty) {
            map_danger[x-1][y] = map_danger[x][y]+1;
            Q.push(std::make_pair(x-1, y));
        }
        if(x < m && map_danger[x+1][y] == kEmpty) {
            map_danger[x+1][y] = map_danger[x][y]+1;
            Q.push(std::make_pair(x+1, y));
        }
        if(y > 1 && map_danger[x][y-1] == kEmpty) {
            map_danger[x][y-1] = map_danger[x][y]+1;
            Q.push(std::make_pair(x, y-1));
        }
        if(y < n && map_danger[x][y+1] == kEmpty) {
            map_danger[x][y+1] = map_danger[x][y]+1;
            Q.push(std::make_pair(x, y+1));
        }
    }
    return -1;
}

/**
    Check if an Euler circuit (or chain) does exist.
    @return -1 if impossible, 0 if circuit possible and other positive number with odd degree (if only chain is possible)
*/
int checkEuler() {
    int odd_degree_counter = 0;
    int result = 0;
    for(int i = 1; i <= n_nests; ++i) {
        if(edges[i].size() == 0) return -1;
        if(edges[i].size()%2 == 1) {
            if(odd_degree_counter <= 1) {
                ++odd_degree_counter;
                if(map_danger[nests_coordinates[i][0]][nests_coordinates[i][1]] == kMarkDanger) result = i;
            }
            else return -1;
        }
    }
    if(odd_degree_counter == 1) return -1;
    if(odd_degree_counter == 2 && result == 0) return -1; //the degree-1 nodes are both in danger zones
    return 0;
}

/**
    Build Euler's circuit into euler_circuit vector.
    Careful, it does modifiy the edges lists.
*/
void buildEuler(int x) {
    std::stack<int> S;
    S.push(x);
    while(!S.empty()) {
        if(edges[S.top()].size() > 0) {
            x = edges[S.top()].front();
            if(edges[x].size() == 1 && x != edges[S.top()].back()) {
                x = edges[S.top()].back(); //don't use the other end yet
                edges[S.top()].pop_back();
            }
            else edges[S.top()].pop_front();
            edges[x].erase(std::find(edges[x].begin(), edges[x].end(), S.top()));
            S.push(x);
        }
        else {
            euler_circuit.push_back(S.top());
            S.pop();
        }
    }
}

int main()
{
    std::ifstream in("cartite.in");
    std::ofstream out("cartite.out");
    //read essentials; Carefull, number of rows before number of columns!
    in>>test_type;
    in>>m>>n;
    //read mole
    in>>mole_x>>mole_y;
    //read foxes
    in>>k;
    for(int x, y, z, i = 1; i <= k; ++i) {
        in>>x>>y>>z;
        markDanger(x, y, z);
    }
    //read nests
    in>>g;
    n_nests = 0;
    for(int x1, y1, x2, y2, i = 1; i <= g; ++i) {
        in>>x1>>y1>>x2>>y2;
        if(map_nests[x1][y1] == kEmpty) {
            ++n_nests;
            map_nests[x1][y1] = n_nests;
            nests_coordinates[n_nests][0] = x1;
            nests_coordinates[n_nests][1] = y1;
        }
        if(map_nests[x2][y2] == kEmpty) {
            ++n_nests;
            map_nests[x2][y2] = n_nests;
            nests_coordinates[n_nests][0] = x2;
            nests_coordinates[n_nests][1] = y2;
        }
        edges[map_nests[x1][y1]].push_back(map_nests[x2][y2]);
        edges[map_nests[x2][y2]].push_back(map_nests[x1][y1]);
    }
    int d;
    switch(test_type) {
    case 1:
        d = markLee(mole_x, mole_y);
        out<<mole_x<<' '<<mole_y<<' '<<d<<'\n';
        break;
    case 2:
        int aux = checkEuler();
        if(aux >= 0) {
            bool flag = false;
            if(aux == 0) {
                for(int i = 1; i <= n_nests && !flag; ++i) {
                    if(map_danger[nests_coordinates[i][0]][nests_coordinates[i][1]] != kMarkDanger) {
                        buildEuler(i);
                        flag = true;
                    }
                }
            }
            else {
                buildEuler(aux);
                flag = true;
            }
            if(flag) {
                for(int nest : euler_circuit) {
                    out<<nests_coordinates[nest][0]<<' '<<nests_coordinates[nest][1]<<'\n';
                }
            }
            else out<<"-1\n";
        }
        else out<<"-1\n";
        break;
    }
    return 0;
}