#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

const int nmx = 204;
const int p1[] = {1,-1,0,0}, p2[] = {0,0,1,-1};

int cerinta,xc,yc,vulpi,muchii;
int n,m,mat[nmx][nmx];
int xintrare, yintrare, dintrare;
vector <int> g[40002];
vector <pair<int,int> > ciclu;

void casuta(int nr, int &x, int &y)
{
    x = (nr + m - 1) / m;
    y = (nr - 1) % m + 1;
}

void numar(int &nr, int x, int y)
{
    nr = (x - 1) * m + y;
}

void vulpe(int x, int y, int val)
{
    mat[x][y] = -1;
    if(val > 0)
    {
        mat[x-1][y] = -1;
        mat[x+1][y] = -1;
        mat[x][y-1] = -1;
        mat[x][y+1] = -1;
    }
    if(val > 1)
    {
        mat[x-1][y-1] = -1;
        mat[x-1][y+1] = -1;
        mat[x+1][y+1] = -1;
        mat[x+1][y-1] = -1;
        mat[x+2][y] = -1;
        mat[x][y+2] = -1;
        if(y - 2 > 0)
            mat[x][y-2] = -1;
        if(x - 2 > 0)
            mat[x-2][y] = -1;
    }
}

void citire()
{
    scanf("%d", &cerinta);
    scanf("%d %d", &n, &m);
    scanf("%d %d", &xc , &yc);
    scanf("%d", &vulpi);
    for(int i = 1; i <= vulpi; ++i)
    {
        int x,y,val;
        scanf("%d %d %d", &x, &y, &val);
        vulpe(x,y,val);
    }
    scanf("%d", &muchii);
    for(int i = 1; i <= muchii; ++i)
    {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        if(not mat[x1][y1])
            mat[x1][y1] = -2;
        if(not mat[x2][y2])
            mat[x2][y2] = -2;
        int nod1,nod2;
        numar(nod1,x1,y1);
        numar(nod2,x2,y2);
        g[nod1].push_back(nod2);
        g[nod2].push_back(nod1);
    }
}

void bordare()
{
    for(int i = 0; i <= n + 1; ++i)
        mat[i][0] = mat[i][m+1] = -1;
    for(int i = 0; i <= m + 1; ++i)
        mat[0][i] = mat[n+1][i] = -1;
}

void lee()
{
    queue <pair<int,int> > q;
    mat[xc][yc] = 1;
    q.push(make_pair(xc,yc));

    while(not q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; ++i)
            if(not mat[x+p1[i]][y+p2[i]])
            {
                mat[x+p1[i]][y+p2[i]] = mat[x][y] + 1;
                q.push(make_pair(x+p1[i],y+p2[i]));
            }
            else if(mat[x+p1[i]][y+p2[i]] == -2)
            {
                xintrare = x + p1[i];
                yintrare = y + p2[i];
                dintrare = mat[x][y] + 1;
                return ;
            }
    }
}

void elimin(int nod1, int nod2)
{
    g[nod1].erase(find(g[nod1].begin(),g[nod1].end(),nod2));
    g[nod2].erase(find(g[nod2].begin(),g[nod2].end(),nod1));
}

void euler()
{
    stack <int> st;
    for(int i = 1; i <= n * m; ++i)
        if(g[i].size() > 0)
        {
            st.push(i);
            break;
        }

     while(not st.empty())
     {
         int nod = st.top();
         if(g[nod].size())
         {
             int nod_aux = g[nod].back();
             elimin(nod,nod_aux);
             st.push(nod_aux);
         }
         else
         {
             int x, y;
             casuta(nod,x,y);
             ciclu.push_back(make_pair(x,y));
             st.pop();
         }
     }
}

void afish()
{
    if(cerinta == 1)
    {
        printf("%d %d %d\n", xintrare, yintrare, dintrare - 1);
    }
    else
    {
        for(size_t i = 0; i < ciclu.size(); ++i)
            printf("%d %d\n", ciclu[i].first, ciclu[i].second);
    }
}

int main()
{
    freopen("cartite.in", "r", stdin);
    freopen("cartite.out", "w", stdout);
    bordare();
    citire();
    lee();
    euler();
    afish();
    return 0;
}