#include <bits/stdc++.h>

using namespace std;

ifstream fin("cartite.in");
ofstream fout("cartite.out");
const int MAXN = 210, MAXG = 110;

struct Pos {
    int x, y;
}sol, mole, start = {-1, -1};

struct Edge {
    Pos from, to;
    bool vis;
}edges[MAXG];

int mat[MAXN][MAXN], n, m, p, dx[] = {-1, 1, 0, 0}, dy[]= {0, 0, -1, 1}, dist = MAXN;
bitset<MAXN> gal[MAXN];
queue<Pos> q;
stack<Pos> st;
vector<int> graph[MAXN][MAXN];

void mark(int x, int y, int range) {
    if (range == 0) {
        mat[x][y] = -1;
        return;
    }
    if (range == 1) {
        mat[x][y] = -1;
        for (int k = 0; k < 4; ++k) {
            int newX = x + dx[k], newY = y + dy[k];
            mat[newX][newY] = -1;
        }
        return;
    }
    mat[x][y] = -1;
    for (int k = 0; k < 4; ++k) {
        int newX = x + dx[k], newY = y + dy[k];
        mat[newX][newY] = -1;
        newX = x + 2 * dx[k];
        newY = y + 2 * dy[k];
        mat[newX][newY] = -1;
    }
}

void read() {
    int k, g;
    fin >> p >> n >> m >> mole.x >> mole.y >> k;
    for (int i = 0; i < k; ++i) {
        int x, y, range;
        fin >> x >> y >> range;
        mark(x, y, range);
    }
    fin >> g;
    for (int i = 0; i < g; ++i) {
        Pos from, to;
        fin >> from.x >> from.y >> to.x >> to.y;
        edges[i] = {from, to, false};
        graph[from.x][from.y].push_back(i);
        graph[to.x][to.y].push_back(i);
        gal[from.x][from.y] = 1;
        gal[to.x][to.y] = 1;
        if (mat[from.x][from.y] != -1 && start.x == -1)
            start = from;
        else if (mat[to.x][to.y] != -1 && start.x == -1)
            start = to;
    }
}

bool inMatrix(int x, int y) {
    if (x < 1 || y < 1 || x >= n || y >= m)
        return false;
    if (x == mole.x && y == mole.y)
        return false;
    return true;
}

void lee() {
    if (gal[mole.x][mole.y]) {
        sol = mole;
        dist = 0;
        return;
    }
    q.push(mole);
    while (!q.empty()) {
        Pos pos = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int newX = pos.x + dx[k], newY = pos.y + dy[k];
            if (mat[newX][newY] != -1 && inMatrix(newX, newY) && (mat[newX][newY] > mat[pos.x][pos.y] + 1 || !mat[newX][newY])) {
                mat[newX][newY] = mat[pos.x][pos.y] + 1;
                q.push({newX, newY});
                if (gal[newX][newY] && mat[newX][newY] < dist) {
                    sol.x = newX;
                    sol.y = newY;
                    dist = mat[newX][newY];
                }
            }
        }
    }
}

void euler() {
    st.push(start);
    while (!st.empty()) {
        Pos node = st.top();
        if (graph[node.x][node.y].size() == 0) {
            fout << node.x << ' ' << node.y << '\n';
            st.pop();
            continue;
        }
        int last = graph[node.x][node.y].back();
        Pos from = edges[last].from, to = edges[last].to;
        graph[node.x][node.y].pop_back();
        if (edges[last].vis)
            continue;
        if (from.x != node.x || from.y != node.y) {
            to.x = from.x;
            to.y = from.y;
        }
        st.push(to);
        edges[last].vis = true;
    }
}

int main() {
    read();
    if (p == 1) {
        lee();
        fout << sol.x << ' ' << sol.y << ' ' << dist;
    }
    else
        euler();
    return 0;
}