#include<stdio.h>
#include<vector>
#include<limits.h>
#define NRDIR 4
#define MAXN 200
#define MAXG 100
void Bordaj(int,int);
void bfs();
void dfs(int nod);
int mat[MAXN+1][MAXN+1];
bool viz[MAXN+1][MAXN+1];
bool bloc[MAXN+1][MAXN+1];
bool mat_adiac[2*MAXG+1][2*MAXG+1];
int d[MAXN+1][MAXN+1];
int dirx[NRDIR]= {1,-1,0,0};
int diry[NRDIR]= {0,0,1,-1};

std::vector<int> neighbors[2*MAXG+1];
std::pair<int,int> coord[2*MAXG+1];
bool vizi[2*MAXG+1];

std::pair<int,int> coada[MAXN*MAXN+1];
int pr=0,ult=-1;

std::vector<int> ccl;
FILE*fin,*fout;
int main()
{
    fin=fopen("cartite.in","r");
    fout=fopen("cartite.out","w");
    int v,N,M;
    fscanf(fin,"%d%d%d",&v,&N,&M);
    int xstart,ystart;
    fscanf(fin,"%d%d",&xstart,&ystart);
    int K;
    fscanf(fin,"%d",&K);
    for(int i=1; i<=K; i++)
    {
        int x,y,r;
        fscanf(fin,"%d%d%d",&x,&y,&r);
        for(int k=0; k<=r; k++)
        {
            for(int j=0; j<NRDIR; j++)
            {
                if(x+k*dirx[j]>0 && x+k*dirx[j]<=N)
                {
                    bloc[x+k*dirx[j]][y]=1;
                }
                if(y+k*diry[j]>0 && y+k*diry[j]<=N)
                {
                    bloc[x][y+k*diry[j]]=1;
                }
            }
        }

    }
    int G;
    int k=0;
    fscanf(fin,"%d",&G);
    for(int i=1; i<=G; i++)
    {
        int x1,y1,x2,y2;
        fscanf(fin,"%d%d%d%d",&x1,&y1,&x2,&y2);
        if(mat[x1][y1]==0)
        {
            mat[x1][y1]=++k;
            coord[k]=std::make_pair(x1,y1);
        }

        if(mat[x2][y2]==0)
        {
            mat[x2][y2]=++k;
            coord[k]=std::make_pair(x2,y2);
        }
        neighbors[mat[x1][y1]].push_back(mat[x2][y2]);
        neighbors[mat[x2][y2]].push_back(mat[x1][y1]);
        mat_adiac[mat[x1][y1]][mat[x2][y2]]=1;
        mat_adiac[mat[x2][y2]][mat[x1][y1]]=1;
    }

    Bordaj(N,M);
    viz[xstart][ystart]=1;
    coada[++ult]=std::make_pair(xstart,ystart);
    bfs();
    if(v==1)
    {
        int mindist=INT_MAX;
        std::pair<int,int> ans;
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=M; j++)
            {
                if(mat[i][j]!=0 && viz[i][j] && !bloc[i][j])
                {
                    if(mindist>d[i][j])
                    {
                        mindist=d[i][j];
                        ans=std::make_pair(i,j);
                    }
                }
            }
        }
        fprintf(fout,"%d %d %d",ans.first,ans.second,mindist);
    }
    if(v==2)
    {
        for(int i=1; i<=k; i++)
        {
            if(viz[coord[k].first][coord[k].second] && !vizi[k])
            {
                vizi[k]=1;
                dfs(k);
            }
        }
        for(int i=0;i<ccl.size();i++)
        {
                fprintf(fout,"%d %d\n",coord[ccl[i]].first,coord[ccl[i]].second);
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
void Bordaj(int n,int m)
{
    for(int i=0; i<=n+1; i++)
    {
        bloc[i][0]=1;
        bloc[i][m+1]=1;
    }
    for(int i=0; i<=m+1; i++)
    {
        bloc[0][i]=1;
        bloc[n+1][i]=1;
    }

}
void bfs()
{
    while(pr<=ult)
    {
        int x=coada[pr].first,y=coada[pr].second;
        for(int i=0; i<NRDIR; i++)
        {
            if(!viz[x+dirx[i]][y+diry[i]] && !bloc[x+dirx[i]][y+diry[i]])
            {
                viz[x+dirx[i]][y+diry[i]]=1;
                d[x+dirx[i]][y+diry[i]]=d[x][y]+1;
                coada[++ult]=std::make_pair(x+dirx[i],y+diry[i]);
            }
        }
        pr++;
    }
}
void dfs(int nod)
{
    int vec=0;
    while(!neighbors[nod].empty())
    {
        int vec=neighbors[nod].back();
        if(mat_adiac[vec][nod])
        {
            mat_adiac[nod][vec]=0;
            mat_adiac[vec][nod]=0;
            neighbors[nod].pop_back();
            vizi[vec]=1;
            dfs(vec);
        }
        else
        {
            mat_adiac[nod][vec]=0;
            mat_adiac[vec][nod]=0;
            neighbors[nod].pop_back();
        }

    }
    ccl.push_back(nod);
}