#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream in("cartite.in");
ofstream out("cartite.out");

typedef pair < bool , pair < int, int > > Pair;
const int NMAX=210, dX[]= {-1, 0, 1, 0, -2, -1, 0, 1, 2, 1, 0, -1}, dY[]= {0, 1, 0, -1, 0, 1, 2, 1, 0, -1, -2, -1};
int Question, n, m, xc, yc, K, G, Mat[NMAX][NMAX], a[NMAX][NMAX], rX, rY;
deque < pair < int, int > > Q;
map < pair < int, int >, vector < pair < bool, pair < int, int > > > > MAP;
vector < pair < int, int > > R;

void Mark(int x, int y, int c)
{
    int z=-1, NewX, NewY;
    Mat[x][y] = -1;
    if(c == 1)
        z = 3;
    if(c == 2)
        z = 11;
    for(int i = 0; i <=z; i++)
    {
        NewX = x + dX[i];
        NewY = y + dY[i];
        if(NewX < 1 || NewX > n || NewY < 1 || NewY > m)
            continue;
        Mat[NewX][NewY] = -1;
    }
}

bool INSIDE(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m)
        return 0;
    return 1;
}

void Lee(int x, int y)
{
    if(Mat[x][y] == 1)
    {
        rX = x;
        rY = y;
        return;
    }
    a[x][y]=1;
    int NewX, NewY;
    Q.push_back(make_pair(x, y));
    while(!Q.empty())
    {
        x = Q.front().first;
        y = Q.front().second;
        Q.pop_front();
        for(int z = 0; z < 4; z++)
        {
            NewX = x + dX[z];
            NewY = y + dY[z];
            if(INSIDE(NewX, NewY) && !a[NewX][NewY] && Mat[NewX][NewY]!=-1)
            {
                Q.push_back(make_pair(NewX, NewY));
                a[NewX][NewY] = a[x][y] + 1;
                if(Mat[NewX][NewY] == 1)
                {
                    rX = NewX;
                    rY = NewY;
                    return;
                }
            }
        }
    }
}

void DFS(int x, int y)
{
    for(Pair it : MAP[{x, y}])
        if(it.first)
        {
            it.first = 0;
            for(Pair i : MAP[{it.second.first, it.second.second}])
                if(i.second.first == x && i.second.second == y)
                {
                    i.first = 0;
                    break;
                }
            DFS(it.second.first, it.second.second);
        }
    R.push_back(make_pair(x, y));

}

void Read_Solve()
{
    ios::sync_with_stdio(false);
    in.tie(NULL);
    int x1, y1, x2, y2;
    in >> Question >> n >> m >> xc >> yc >> K;
    for(int i = 1; i <= K; i++)
    {
        in >> x1 >> y1 >> x2;
        Mark(x1, y1, x2);
    }
    in >> G;
    for(int i = 1; i <= G; i++)
    {
        in >> x1 >> y1 >> x2 >> y2;
        MAP[ {x1, y1}].push_back({1, {x2, y2}});
        MAP[ {x2, y2}].push_back({1, {x1, y1}});
        if(!Mat[x1][y1])
            Mat[x1][y1] = 1;
        if(!Mat[x2][y2])
            Mat[x2][y2] = 1;
    }
    if(Question == 1)
    {
        Lee(xc, yc);
        out << rX << ' ' << rY << ' ' << a[rX][rY]-1;
        return;
    }
    DFS(x1, y1);
    for(pair < int, int > it : R)
        out << it.first << ' ' << it.second << '\n';
}

int main()
{
    Read_Solve();
    return 0;
}