#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <algorithm>
#define nmax 205
#define maxim 42000
#define inf 1000000000
using namespace std;

int n, m, p, cartx, carty, k, gal, gal1;
int ferma[nmax][nmax]; ///zona "agricola"
ifstream f("cartite.in");
ofstream g("cartite.out");
queue <pair <int, int> > q;
const int dx[]={0, 1, 0, -1};
const int dy[]={1, 0, -1, 0};
vector <vector <int> > G(maxim);
vector <int> sol;
stack <int> eul;

void add_vulpe(const int &x, const int &y, const int &r)
{               /// se marcheaza cu -1 zona cu vulpi
    if(!r)
    {
        ferma[x][y] = -1;
    }
    else
    if(r==1)
    {
        ferma[x][y] = -1;
        ferma[x][y+1] = -1;
        ferma[x][y-1] = -1;
        ferma[x+1][y] = -1;
        ferma[x-1][y] = -1;
    }
    if(r==2)
    {
        ferma[x][y] = -1;
        ferma[x][y+1] = -1;
        ferma[x][y-1] = -1;
        ferma[x+1][y] = -1;
        ferma[x-1][y] = -1;

        if(y+2<=n+1)
        ferma[x][y+2] = -1;
        if(y-2>=0)
        ferma[x][y-2] = -1;
        if(x+2<=m+1)
        ferma[x+2][y] = -1;
        if(x-2>=0)
        ferma[x-2][y] = -1;

        ferma[x+1][y+1] = -1;
        ferma[x+1][y-1] = -1;
        ferma[x-1][y-1] = -1;
        ferma[x-1][y+1] = -1;
    }

}

void read()
{
    f >> p >> m >> n;
    f >> cartx >> carty;
    f >> k;
    for(int i=0, xc, yc, raza; i<k; ++i)
    {
       f >> xc >> yc >> raza;
       add_vulpe(xc, yc, raza);
    }
    f >> gal;
    for(int i=0, x1, y1, x2, y2, nod1, nod2; i<gal; ++i)
    {
        f >> x1 >> y1 >> x2 >> y2;
        nod1 = x1 * n - n + y1;   ///transf poz (x,y) --> nr (nod)
        nod2 = x2 * n - n + y2;
        if(ferma[x1][y1]!=-1) gal1=nod1; ///de unde incep sa parcurg galeria
        G[nod1].push_back(nod2); ///lista cu galeriile (intrari/iesiri)
        G[nod2].push_back(nod1);
        if(ferma[x1][y1] != -1) ///marchez cu o val mare intrarea in galerii
        ferma[x1][y1] = inf;    ///daca nu sunt in zona cu vulpi
        if(ferma[x1][y1] != -1)
        ferma[x2][y2] = inf;
    }
    f.close();
}

void cer_a()
{
    pair <int, int> xx, yy;
    int xf, yf, dist=1;
    for(int i=0; i<=m+1; ++i) ///bordez cu -1
    ferma[i][0] = -1, ferma[i][n+1] = -1;
    for(int i=0; i<=n+1; ++i)
    ferma[0][i] = -1, ferma[m+1][i] = -1;

    q.push(make_pair(cartx, carty)); ///retin in coada traseu

    if(ferma[cartx][carty] == inf)
    {
        g << cartx << ' ' << carty << ' ' << dist-1;
        g.close();
        return;
    }

    ferma[cartx][carty] = 1;
    while(!q.empty())
    {
        xx = q.front(); q.pop(); ///caut cu Lee o galerie
        for(int k=0; k<4; ++k)
        {
            yy.first = xx.first + dx[k];
            yy.second = xx.second + dy[k];
            if(ferma[yy.first][yy.second] == inf) ///am gasit o galerie
            {
                xf = yy.first;
                yf = yy.second;
                dist = ferma[xx.first][xx.second] + 1;
                while(!q.empty()) q.pop();
            }
            if(ferma[yy.first][yy.second] == 0) ///pot inainta
            {
                ferma[yy.first][yy.second] = ferma[xx.first][xx.second] + 1;
                q.push(make_pair(yy.first, yy.second));
            }
        }
    }
    g << xf << ' ' << yf << ' ' << dist-1 << '\n'; ///coord galeriei
    g.close();
}

void cer_b()
{
    int xx, yy;
    xx = gal1;
    eul.push(xx); ///se construieste un ciclu eulerian
    while(!eul.empty())
    {
        xx = eul.top();
        if(G[xx].size())
        {
            yy = G[xx].back();
            G[xx].pop_back();
            G[yy].erase(find(G[yy].begin(), G[yy].end(), xx));
            eul.push(yy);
        }
        else
        {
            xx=eul.top();
            sol.push_back(xx);
            eul.pop();
        }
    }
    for(int i=0, a, b; i<sol.size(); ++i)
    {
        if(sol[i]%n==0) {
            a = sol[i]/n;
            b = n;
            g << a << ' ' << b << '\n';
        }
        else {
        a = sol[i]/n + 1;
        b = sol[i]%n;
        g << a << ' ' << b << '\n';
        }
    }
    g.close();

}

int main()
{
    read();
    if(p==1)
        cer_a();
    else
        cer_b();
    return 0;
}