#include <fstream>
#include <queue>
#include <vector>
#include <deque>

using namespace std;

bool okay (unsigned short int i, unsigned short int j);

unsigned short int p;
unsigned short int M, N;
unsigned short int XC, YC;
unsigned short int K;
unsigned short int x[51], y[51], r[51];
unsigned short int G;
unsigned short int x1[101], y1[101], x2[101], y2[101];

vector < unsigned short int > GV[201], HV[201];
deque < unsigned short int > DQ;
queue < pair < unsigned short int, unsigned short int > > Q;
const short int dx[] = {-1,  0,  1,  0};
const short int dy[] = { 0,  1,  0, -1};
int matrix[201][201];
unsigned short int solx[101], soly[101];
int solution[101], degree[101];
bool seen[201];
short int minimum;
unsigned short int node, xx, yy;
unsigned short int i, j, k, w, nextI, nextJ;

unsigned short int x3, y3;
unsigned long int dist;
unsigned short int X[10001], Y[10001];

int main ()
{
    /// Read
    ifstream fin ("cartite.in");
    fin >> p;
    fin >> M >> N;
    fin >> XC >> YC;
    fin >> K;
    for (i=1; i<=K; i++)
        fin >> x[i] >> y[i] >> r[i];
    fin >> G;
    for (i=1; i<=G; i++)
        fin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    fin.close();

    /// Initialization
    for (i=1; i<=K; i++)
    {
        if (r[i] == 0)
            matrix[x[i]][y[i]] = -1;
        else if (r[i] == 1)
        {
            matrix[x[i]][y[i]] = -1;
            matrix[x[i]-1][y[i]] = -1;
            matrix[x[i]][y[i]+1] = -1;
            matrix[x[i]+1][y[i]] = -1;
            matrix[x[i]][y[i]-1] = -1;
        }
        else
        {
            matrix[x[i]][y[i]] = -1;
            matrix[x[i]-1][y[i]] = -1;
            matrix[x[i]][y[i]+1] = -1;
            matrix[x[i]+1][y[i]] = -1;
            matrix[x[i]][y[i]-1] = -1;
            matrix[x[i]-2][y[i]] = -1;
            matrix[x[i]][y[i]+2] = -1;
            matrix[x[i]+2][y[i]] = -1;
            matrix[x[i]][y[i]-2] = -1;
            matrix[x[i]-1][y[i]+1] = -1;
            matrix[x[i]+1][y[i]+1] = -1;
            matrix[x[i]+1][y[i]-1] = -1;
            matrix[x[i]-1][y[i]-1] = -1;
        }
    }

    /// Algorithm /// First
    matrix[XC][YC] = 0;
    Q.push(make_pair(XC,YC));
    while (!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (k=0; k<4; k++)
        {
            nextI = i + dx[k];
            nextJ = j + dy[k];
            if (okay(nextI,nextJ) == 1 && matrix[nextI][nextJ] == 0)
            {
                matrix[nextI][nextJ] = matrix[i][j] + 1;
                Q.push(make_pair(nextI,nextJ));
            }
            else if (okay(nextI,nextJ) == 1 && matrix[nextI][nextJ] > 0 && matrix[nextI][nextJ] > matrix[i][j]+1)
            {
                matrix[nextI][nextJ] += matrix[i][j];
                Q.push(make_pair(nextI,nextJ));
            }
        }
    }
    for (i=1; i<=G; i++)
    {
        if (matrix[x[i]][y[i]] == -1)
            solution[i] = 0;
        else
            solution[i] = matrix[x1[i]][y1[i]];
        solx[i] = x1[i];
        soly[i] = y1[i];
    }
    for (i=1; i<=G; i++)
        if (solution[i] > 0)
        {
            minimum = solution[i];
            x3 = solx[i];
            y3 = soly[i];
            break;
        }
    for (i=1; i<=G; i++)
        if (solution[i] < minimum && solution[i] > 0)
        {
            minimum = solution[i];
            x3 = solx[i];
            y3 = soly[i];
        }
    dist = minimum;

    /// Second
    for (i=1; i<=G; i++)
    {
        GV[x1[i]].push_back(y1[i]);
        GV[y1[i]].push_back(x1[i]);
        GV[x2[i]].push_back(y2[i]);
        GV[y2[i]].push_back(x2[i]);
        HV[x1[i]].push_back(i);
        HV[y1[i]].push_back(i);
        HV[x2[i]].push_back(i);
        HV[y2[i]].push_back(i);
        degree[x1[i]]++;
        degree[y1[i]]++;
        degree[x2[i]]++;
        degree[y2[i]]++;
    }
    w = 0;
    DQ.push_back(1);
    while (!DQ.empty())
    {
        node = DQ.back();
        if (degree[node] == 0)
        {
            X[i] = node;
            Y[i] = node;
            DQ.pop_back();
            w++;
        }
        else
        {
            xx = GV[node].back();
            yy = HV[node].back();
            GV[node].pop_back();
            HV[node].pop_back();
            if (seen[yy] == 0)
            {
                seen[yy] = 1;
                DQ.push_back(xx);
                degree[xx]--;
                degree[node]--;
            }
        }
    }

    /// Print
    ofstream fout ("cartite.out");
    if (p == 1)
        fout << x3 << ' ' << y3 << ' ' << dist;
    else
    {
        /// Temp
        for (i=1; i<=w; i++)
        {
            fout << X[i] << ' ' << Y[i];
            fout << '\n';
        }
    }
    fout.close();
    return 0;
}

bool okay (unsigned short int i, unsigned short int j)
{
    if (i<1 || j<1 || i>M || j>N)
        return 0;
    return 1;
}