#include<bits/stdc++.h>
using namespace std;
ifstream F("cartite.in");
ofstream G("cartite.out");
int n,m,a[201][201],b,c,d,k,g,x[]={-1,0,1,0},l,t,p,q,r,s,u,v,w,e,f[40001],i,B[40001],C[40001],U,V,D,E,H[201][201],Z=40001,j;
list<int> z[40001];
int main()
{
    for(F>>b>>n>>m>>c>>d>>k,e=max(n,m);k--;)
        if(F>>u>>v>>w,!w)
            a[u][v]=1;
        else if(w==1) {
            for(a[u][v]=1,l=0;l<4;++l)
                if(u+x[l]&&v+x[3-l]&&u+x[l]<=n&&v+x[3-l]<=m)
                    a[u+x[l]][v+x[3-l]]=1;
        } else
            for(a[u][v]=1,l=-2;l<3;++l)
                for(t=-2;t<3;++t)
                    if(abs(l)+abs(t)<3&&u+l>0&&v+t>0&&u+l<=n&&v+t<=m)
                        a[u+l][v+t]=1;
    for(u=0,w=0,F>>g;g--;) {
        if(F>>p>>q>>r>>s,z[(p-1)*e+q].push_back((r-1)*e+s),!u&&!w&&a[p][r]!=1)
            u=p,w=q;
        if(!a[p][q])
            a[p][q]=2;
        if(!a[r][s])
            a[r][s]=2;
    }
    if(b==2) {
        for(v=1,f[1]=(u-1)*e+w;v;G<<f[v]/e+1<<' '<<f[v]%e<<'\n',--v)
            for(g=f[v];!z[g].empty();)
                i=z[g].front(),z[g].pop_front(),z[i].erase(find(z[i].begin(),z[i].end(),g)),f[++v]=g=i;
        return 0;
    }
    for(U=0,V=0,B[V]=c,C[V++]=d,H[c][d]=1;U<V;++U)
        for(D=B[U],E=C[U],k=0;k<4;++k)
            if(D+x[k]&&E+x[3-k]&&D+x[k]<=n&&E+x[3-k]<=m&&!H[D+x[k]][E+x[3-k]]&&a[D+x[k]][E+x[3-k]]!=1)
                H[D+x[k]][E+x[3-k]]=H[D][E]+1,B[V]=D+x[k],C[V++]=E+x[3-k];
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(a[i][j]==2&&Z>H[i][j]-1)
                Z=H[i][j]-1,k=i,l=j;
    return G<<k<<' '<<l<<' '<<Z,0;
}