#include <iostream>
#include <stdio.h>
#include <time.h>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string.h>
using namespace std;

struct Flow
{
    int x1,y1,x2,y2;
    int id;
};

int help=0;
int sumtime=0;
bool DEBUG=false;

Flow Flows[501];
vector< pair<int,int> > FlowPath[501];

bool Blocked[111][111];
bool Flowed[111][111];
bool EndPoint[111][111];
int n;
int p,B;
int TFO[111][111];
int Key=1;

int EndPointRiver[111][111];

int TIME_LIMIT=4*CLOCKS_PER_SEC+CLOCKS_PER_SEC/2;
bool TimeIsOK()
{
    return clock()<TIME_LIMIT;
}

int GX,GY;
int SX,SY;
vector< pair<int,int> > Path;

pair<int,int> Moves[5];

bool OK(int x,int y)
{
    if (x<1 || x>n || y<1 || y>n)
    return false;
    if (TFO[x][y]==Key)
    return false;
    if (Blocked[x][y])
    return false;
    if (Flowed[x][y])
    return false;
    if (EndPoint[x][y] && (x!=GX || y!=GY) && (x!=SX || y!=SY) )
    return false;

    return true;
}


bool DFS(int x,int y)
{
    if (!OK(x,y))
    return false;

    TFO[x][y]=Key;

    Path.push_back(make_pair(x,y));

    if (x==GX && y==GY)
    return true;

    int i;

    for (i=1;i<=4;i++)
    {
        if ( DFS(x+Moves[i].first,y+Moves[i].second) )
        return true;
    }

    Path.pop_back();

    return false;
}

int Seen[301];

void FindRivers(int x,int y)
{
    if (x<1 || x>n || y<1 || y>n)
    return;
    if (TFO[x][y]==Key)
    return;
    if (Blocked[x][y])
    return;
    if (Flowed[x][y])
    return;

    int i;

    TFO[x][y]=Key;

    if (EndPointRiver[x][y]!=0)
    {
        if ( (x!=SX || y!=SY) && (x!=GX || y!=GY) )
        {
            Seen[ EndPointRiver[x][y] ]++;
            return;
        }
    }

    for (i=1;i<=4;i++)
    {
        FindRivers(x+Moves[i].first,y+Moves[i].second);
    }

    return;
}

int comefrom[100001];
pair<int,int> q[100001];
int qL=0;

void BFS(int x,int y)
{
    int uk=1;
    int i;
    int rem=-1;

    qL=1;
    q[1]=make_pair(x,y);
    comefrom[1]=0;
    TFO[x][y]=Key;

    while(uk<=qL)
    {
        x=q[uk].first;
        y=q[uk].second;

        if (x==GX && y==GY)
        {
            rem=uk;
            break;
        }

        for (i=1;i<=4;i++)
        {
            if (OK(x+Moves[i].first,y+Moves[i].second))
            {
                qL++;
                q[qL]=make_pair(x+Moves[i].first,y+Moves[i].second);
                comefrom[qL]=uk;
                TFO[ x+Moves[i].first ][ y+Moves[i].second ]=Key;
            }
        }

        uk++;
    }

    if (rem==-1)
    return;

    while(rem!=0)
    {
        Path.push_back( q[rem] );
        rem=comefrom[rem];
    }

    reverse(Path.begin(),Path.end());

    return;
}

vector< pair<int,int> > BestPath[501];
int BestValue=0;

void Evaluate()
{
    int paths=0;
    int flooded=0;
    int i,j;
    int Value;

    for (i=1;i<=p;i++)
    {
        if (!FlowPath[i].empty())
        paths++;

        flooded+=FlowPath[i].size();
    }

    Value=flooded*paths;

    //fprintf(stderr,"Value = %d\n",Value);

    if (Value>BestValue)
    {
        BestValue=Value;

        ///fprintf(stderr,"%dx%d\n",paths,flooded);

        for (i=1;i<=p;i++)
        {
            BestPath[i].clear();

            for (j=0;j<FlowPath[i].size();j++)
            {
                BestPath[i].push_back(FlowPath[i][j]);
            }
        }
    }

    return;
}

vector< pair<int,int> > LongestPath;
vector<int> Added;

void CLEAR(int k)
{
    int i;

    for (i=0;i<FlowPath[k].size();i++)
    {
        Flowed[ FlowPath[k][i].first ][ FlowPath[k][i].second ]=false;
    }

    FlowPath[k].clear();

    return;
}

int main()
{
    //freopen("sample.txt","r",stdin);
    freopen("flow.in","r",stdin);
    freopen("flow.out","w",stdout);

    int i,j,in;
    int x,y;
    int iterations=0;
    int counter=0;
    bool inc;

    srand(30117);

    Moves[1]=make_pair(1,0);
    Moves[2]=make_pair(0,1);
    Moves[3]=make_pair(-1,0);
    Moves[4]=make_pair(0,-1);

    scanf("%d %d",&n,&p);

    for (i=1;i<=p;i++)
    {
        scanf("%d %d %d %d",&Flows[i].x1,&Flows[i].y1,&Flows[i].x2,&Flows[i].y2);
        Flows[i].x1++;
        Flows[i].y1++;
        Flows[i].x2++;
        Flows[i].y2++;

        Flows[i].id=i;
        EndPoint[ Flows[i].x1 ][ Flows[i].y1 ]=true;
        EndPoint[ Flows[i].x2 ][ Flows[i].y2 ]=true;

        EndPointRiver[ Flows[i].x1 ][ Flows[i].y1 ]=Flows[i].id;
        EndPointRiver[ Flows[i].x2 ][ Flows[i].y2 ]=Flows[i].id;
    }

    scanf("%d",&B);

    for (i=1;i<=B;i++)
    {
        scanf("%d %d",&x,&y);
        x++;
        y++;

        Blocked[x][y]=true;
    }

    while(TimeIsOK())
    {
        iterations++;

        for (i=1;i<=p;i++)
        {
            FlowPath[i].clear();
        }

        random_shuffle(Flows+1,Flows+1+p);
        memset(Flowed,0,sizeof(Flowed));

        counter=0;
        for (i=1;i<=p;i++)
        {
            Key++;

            GX=Flows[i].x2;
            GY=Flows[i].y2;
            SX=Flows[i].x1;
            SY=Flows[i].y1;

            Path.clear();
            BFS(SX,SY);

            if (!Path.empty())
            {
                counter++;

                for (j=0;j<Path.size();j++)
                {
                    Flowed[ Path[j].first ][ Path[j].second ]=true;
                    FlowPath[ Flows[i].id ].push_back( Path[j] );
                }
            }
        }


        //fprintf(stderr,"%d vs ",counter);
        inc=true;

        sumtime=0;
        while(inc && TimeIsOK())
        {
            sumtime++;
            help=0;
            inc=false;

            for (i=1;i<=p;i++)
            {
                if (!FlowPath[ Flows[i].id ].empty())
                {
                    CLEAR(Flows[i].id);

                    Key++;
                    Path.clear();

                    GX=Flows[i].x2;
                    GY=Flows[i].y2;
                    SX=Flows[i].x1;
                    SY=Flows[i].y1;

                    memset(Seen,0,sizeof(Seen));

                    FindRivers(SX,SY);

                    Seen[ Flows[i].id ]=2;

                    Added.clear();

                    for (j=1;j<=p;j++)
                    {
                        if (i==j || !FlowPath[ Flows[j].id ].empty())
                        continue;

                        if (Seen[ Flows[j].id ]<2)
                        continue;

                        Key++;

                        GX=Flows[j].x2;
                        GY=Flows[j].y2;
                        SX=Flows[j].x1;
                        SY=Flows[j].y1;

                        Path.clear();
                        BFS(SX,SY);

                        if (Path.empty())
                        continue;

                        Added.push_back(j);
                        for (in=0;in<Path.size();in++)
                        {
                            Flowed[ Path[in].first ][ Path[in].second ]=true;
                            FlowPath[ Flows[j].id ].push_back( Path[in] );
                        }
                    }

                    ///
                    Key++;

                    GX=Flows[i].x2;
                    GY=Flows[i].y2;
                    SX=Flows[i].x1;
                    SY=Flows[i].y1;

                    Path.clear();
                    BFS(SX,SY);

                    if (!Path.empty())
                    {
                        for (j=0;j<Path.size();j++)
                        {
                            Flowed[ Path[j].first ][ Path[j].second ]=true;
                            FlowPath[ Flows[i].id ].push_back( Path[j] );
                        }
                    }
                    ///

                    if (Added.size()<=1)
                    {
                        ///Failure
                    }
                    else
                    {
                        /*
                        cout<<"Success removing "<<i<<" replacing it with :"<<endl;

                        for (j=0;j<Added.size();j++)
                        {
                            cout<<Added[j]<<" ";
                        }
                        cout<<endl;
                        */

                        counter+=(int)Added.size()-1;
                        inc=true;
                    }
                }
            }
        }

        //fprintf(stderr,"%d\n",counter);

        for (i=1;i<=p;i++)
        {
            if (!FlowPath[ Flows[i].id ].empty())
            {
                Key++;

                GX=Flows[i].x2;
                GY=Flows[i].y2;
                SX=Flows[i].x1;
                SY=Flows[i].y1;

                for (j=0;j<(int)FlowPath[ Flows[i].id ].size();j++)
                {
                    Flowed[ FlowPath[ Flows[i].id ][j].first ][ FlowPath[ Flows[i].id ][j].second ]=false;
                }

                Key++;
                Path.clear();
                LongestPath.clear();
                DFS(SX,SY);

                for (j=0;j<Path.size();j++)
                {
                    LongestPath.push_back(Path[j]);
                }

                sort(Moves+1,Moves+1+4);

                do
                {
                    Path.clear();
                    Key++;

                    DFS(SX,SY);

                    if (Path.size()>LongestPath.size())
                    {
                        LongestPath.clear();

                        for (in=0;in<Path.size();in++)
                        {
                            LongestPath.push_back(Path[in]);
                        }
                    }
                }while( next_permutation(Moves+1,Moves+1+4) );

                FlowPath[ Flows[i].id ].clear();
                for (j=0;j<LongestPath.size();j++)
                {
                    Flowed[ LongestPath[j].first ][ LongestPath[j].second ]=true;
                    FlowPath[ Flows[i].id ].push_back(LongestPath[j]);
                }
            }
        }

        Evaluate();
    }

    for (i=1;i<=p;i++)
    {
        if (BestPath[i].empty())
        printf("0\n");
        else
        {
            printf("%d",BestPath[i].size());
            for (j=0;j<BestPath[i].size();j++)
            {
                printf(" %d %d",BestPath[i][j].first-1,BestPath[i][j].second-1);
            }
            printf("\n");
        }
    }

    fprintf(stderr,"Expected value : %d\n",BestValue);
    fprintf(stderr,"Iterations : %d\n",iterations);

    return 0;