/*
ID: espr1t
TASK: Flow
KEYWORDS: NP, BFS, Greedy
*/

#include <cstdio>
#include <ctime>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>

using namespace std;
const int MAX = 500;
const int SIZE = 100;

const bool DEBUG_INFO = false;
const double MAX_SWAP_TIME = 1.7;
const double MAX_RAND_TIME = 3.2;
const double MAX_EXEC_TIME = 4.2;

struct Cell {
    int row, col;
    Cell(int row_ = 0, int col_ = 0) : row(row_), col(col_) {}

    bool operator == (const Cell& r) const {
        return row == r.row && col == r.col;
    }
    bool operator < (const Cell& r) const {
        return row != r.row ? row < r.row : col < r.col;
    }
};

unsigned sTime;

int boardSize;
int numRivers, numBases;
Cell rivers[MAX][2], bases[MAX];
bool cross[MAX][MAX];

int board[SIZE][SIZE];
int last[SIZE][SIZE], go[SIZE][SIZE];

int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

int answerValue;
vector <int> answerOrder;

int calculateAnswer() {
    vector <int> connected(numRivers, 0);
    int coveredCells = 0;
    for (int row = 0; row < boardSize; row++) {
        for (int col = 0; col < boardSize; col++) {
            int river = board[row][col] - 1;
            if (river >= 0 && go[rivers[river][1].row][rivers[river][1].col] == -2) {
                coveredCells++;
                connected[river] = 1;
            }
        }
    }
    return coveredCells * accumulate(connected.begin(), connected.end(), 0);
}

bool continuousRiver(int row1, int col1, int row2, int col2) {
    if (board[row1][col1] <= 0 || board[row1][col1] != board[row2][col2])
        return false;
    if (row1 + dir[go[row1][col1]][0] != row2)
        return false;
    if (col1 + dir[go[row1][col1]][1] != col2)
        return false;
    return true;
}

void extendRivers() {
    bool changed = true;
    while (changed) {
        changed = false;
        for (int row = 0; row < boardSize; row++) {
            for (int col = 0; col < boardSize; col++) {
                if (board[row][col] != 0)
                    continue;
                for (int d = 0; d < 4; d++) {
                    int nrow = row + dir[d][0]; if (nrow < 0 || nrow >= boardSize) continue;
                    int ncol = col + dir[d][1]; if (ncol < 0 || ncol >= boardSize) continue;
                    if (board[nrow][ncol] != 0)
                        continue;

                    for (int o = 0; o < 4; o++) if (o % 2 != d % 2) {
                        int row1 = row + dir[o][0]; if (row1 < 0 || row1 >= boardSize) continue;
                        int col1 = col + dir[o][1]; if (col1 < 0 || col1 >= boardSize) continue;
                        int row2 = row1 + dir[d][0]; if (row2 < 0 || row2 >= boardSize) continue;
                        int col2 = col1 + dir[d][1]; if (col2 < 0 || col2 >= boardSize) continue;
                        if (!continuousRiver(row1, col1, row2, col2))
                            continue;
                        
                        board[row][col] = board[nrow][ncol] = board[row1][col1];
                        go[row1][col1] = (o + 2) % 4, go[row][col] = d, go[nrow][ncol] = o;
                        changed = true;
                        break;
                    }
                    if (board[row][col] != 0)
                        break;
                }
            }
        }
    }
}

void createRiver(int idx) {
    for (int row = 0; row < boardSize; row++)
        for (int col = 0; col < boardSize; col++)
            last[row][col] = -1;
    
    Cell cur, nxt = rivers[idx][0];
    queue <Cell> q;
    board[rivers[idx][0].row][rivers[idx][0].col] = 0;
    board[rivers[idx][1].row][rivers[idx][1].col] = 0;
    q.push(nxt), last[nxt.row][nxt.col] = -2;
    while (!q.empty()) {
        cur = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            nxt.row = cur.row + dir[i][0]; if (nxt.row < 0 || nxt.row >= boardSize) continue;
            nxt.col = cur.col + dir[i][1]; if (nxt.col < 0 || nxt.col >= boardSize) continue;
            if (board[nxt.row][nxt.col] != 0 || last[nxt.row][nxt.col] != -1)
                continue;
            last[nxt.row][nxt.col] = (i + 2) % 4;
            q.push(nxt);
            if (nxt == rivers[idx][1])
                break;
        }
    }
    
    if (last[rivers[idx][1].row][rivers[idx][1].col] != -1) {
        cur = rivers[idx][1];
        go[cur.row][cur.col] = -2;
        board[cur.row][cur.col] = idx + 1;
        while (last[cur.row][cur.col] != -2) {
            nxt.row = cur.row + dir[last[cur.row][cur.col]][0];
            nxt.col = cur.col + dir[last[cur.row][cur.col]][1];
            go[nxt.row][nxt.col] = (last[cur.row][cur.col] + 2) % 4;
            cur = nxt;
            board[cur.row][cur.col] = idx + 1;
        }
    }
    board[rivers[idx][0].row][rivers[idx][0].col] = idx + 1;
    board[rivers[idx][1].row][rivers[idx][1].col] = idx + 1;
}

int eval(const vector<int>& order) {
    // Initialize board
    //   >> cell with value -1 is a base
    //   >> cell with value 0 is empty
    //   >> cell with value [1, numRivers] is part of a river
    for (int row = 0; row < boardSize; row++)
        for (int col = 0; col < boardSize; col++)
            board[row][col] = 0, go[row][col] = -1;
    
    for (int i = 0; i < numBases; i++)
        board[bases[i].row][bases[i].col] = -1;
    for (int i = 0; i < numRivers; i++) {
        board[rivers[i][0].row][rivers[i][0].col] = i + 1;
        board[rivers[i][1].row][rivers[i][1].col] = i + 1;
    }
    
    // Try creating the rivers
    for (int i = 0; i < (int)order.size(); i++) {
        createRiver(order[i]);
    }
    
    // Try extending the rivers
    extendRivers();
    
    // Update answer if necessary
    int curAnswer = calculateAnswer();
    if (answerValue < curAnswer) {
        answerValue = curAnswer;
        answerOrder = order;
    }
    return curAnswer;
}

void improve(vector <int> order) {
    int bestAnswer = eval(order);
    for (int dist = 1; dist <= 50; dist++) {
        if (DEBUG_INFO) {
            fprintf(stderr, "  >> at dist %d.\n", dist);
        }
        if ((double)(clock() - sTime) / CLOCKS_PER_SEC > MAX_EXEC_TIME)
            break;
        bool improved = false;
        for (int i = 0; i + dist < (int)order.size(); i++) {
            if (i % 10 == 0 && (double)(clock() - sTime) / CLOCKS_PER_SEC > MAX_EXEC_TIME)
                break;

            swap(order[i], order[i + dist]);
            int curAnswer = eval(order);
            if (bestAnswer < curAnswer) {
                bestAnswer = curAnswer;
                improved = true;
                if (DEBUG_INFO) {
                    fprintf(stderr, "  -- improved answer to %d\n", bestAnswer);
                }
            } else {
                swap(order[i], order[i + dist]);
            }
        }
        if (improved) {
            dist = max(0, dist / 2 - 1);
        }
    }
}

void greedyByIntersectionsRandomized() {
    vector < pair <int, int> > order;
    for (int i = 0; i < numRivers; i++) {
        int numIntersections = 0;
        for (int c = 0; c < numRivers; c++)
            numIntersections += cross[i][c];
        order.push_back(make_pair(numIntersections, i));
    }
    sort(order.begin(), order.end());
    while ((double)(clock() - sTime) / CLOCKS_PER_SEC < MAX_SWAP_TIME) {
        vector <int> send;
        for (int i = 0; i < (int)order.size(); i++)
            send.push_back(order[i].second);
        for (int i = (int)send.size() - 1; i > 0; i--) {
            if (rand() % i == 0) swap(send[i], send[i - 1]);
        }
        eval(send);
    }
}

void greedyByIntersections() {
    vector < pair <int, int> > order;
    for (int i = 0; i < numRivers; i++) {
        int numIntersections = 0;
        for (int c = 0; c < numRivers; c++)
            numIntersections += cross[i][c];
        order.push_back(make_pair(numIntersections, i));
    }
    sort(order.begin(), order.end());
    vector <int> send;
    for (int i = 0; i < (int)order.size(); i++)
        send.push_back(order[i].second);
    eval(send);
}

void greedyByLength() {
    vector < pair <int, int> > order;
    for (int i = 0; i < numRivers; i++) {
        int length = abs(rivers[i][0].row - rivers[i][1].row) +
                     abs(rivers[i][0].col - rivers[i][1].col);
        order.push_back(make_pair(length, i));
    }
    sort(order.begin(), order.end());
    vector <int> send;
    for (int i = 0; i < (int)order.size(); i++)
        send.push_back(order[i].second);
    eval(send);
}

void randomOrders() {
    vector <int> order;
    for (int i = 0; i < numRivers; i++)
        order.push_back(i);
    
    while (true) {
        if ((double)(clock() - sTime) / CLOCKS_PER_SEC > MAX_RAND_TIME)
            break;
        random_shuffle(order.begin(), order.end());
        eval(order);
    }
}

int findArea(const Cell& c1, const Cell& c2, const Cell& c3) {
    return c1.row * c2.col + c2.row * c3.col + c3.row * c1.col -
           c1.row * c3.col - c2.row * c1.col - c3.row * c2.col;
}

int lineIntersect(const Cell& c1, const Cell& c2, const Cell& c3, const Cell& c4) {
    int area1 = findArea(c1, c2, c3);
    int area2 = findArea(c1, c2, c4);
    if ((area1 < 0 && area2 < 0) || (area1 > 0 && area2 > 0))
        return false;
    
    int area3 = findArea(c3, c4, c1);
    int area4 = findArea(c3, c4, c2);
    if ((area3 < 0 && area4 < 0) || (area3 > 0 && area4 > 0))
        return false;
    
    // Not perfect line intersection check, but good enough.
    return true;
}

void getIntersections() {
    for (int i = 0; i < numRivers; i++) {
        cross[i][i] = true;
        for (int c = i + 1; c < numRivers; c++) {
            if (lineIntersect(rivers[i][0], rivers[i][1], rivers[c][0], rivers[c][1]))
                cross[i][c] = cross[c][i] = true;
        }
    }
}

void readInput() {
    FILE* in = fopen("flow.in", "rt");

    fscanf(in, "%d", &boardSize);
    fscanf(in, "%d", &numRivers);
    for (int i = 0; i < numRivers; i++) {
        fscanf(in, "%d %d %d %d", &rivers[i][0].row, &rivers[i][0].col,
                                  &rivers[i][1].row, &rivers[i][1].col);
    }
    fscanf(in, "%d", &numBases);
    for (int i = 0; i < numBases; i++) {
        fscanf(in, "%d %d", &bases[i].row, &bases[i].col);
    }
    fclose(in);
}

vector <Cell> getPath(int river) {
    if (go[rivers[river][0].row][rivers[river][0].col] < 0)
        return vector<Cell>();
    Cell cur = rivers[river][0];
    vector <Cell> ret(1, cur);
    while (go[cur.row][cur.col] >= 0) {
        cur = Cell(cur.row + dir[go[cur.row][cur.col]][0],
                   cur.col + dir[go[cur.row][cur.col]][1]);
        ret.push_back(cur);
    }
    return ret;
}

void writeOutput() {
    FILE* out = fopen("flow.out", "wt");

    eval(answerOrder);
    
    if (DEBUG_INFO) {
        vector <int> usedRivers(numRivers, 0);
        for (int i = 0; i < numRivers; i++)
            if (go[rivers[i][0].row][rivers[i][0].col] >= 0)
                usedRivers[i] = 1;
        int usedCells = 0;
        for (int row = 0; row < boardSize; row++) {
            for (int col = 0; col < boardSize; col++) {
                if (board[row][col] > 0 && usedRivers[board[row][col] - 1])
                    usedCells++;
            }
        }
        
        if (DEBUG_INFO) {
            fprintf(stderr, "Answer value: %d\n", answerValue);
            fprintf(stderr, "  >> num rivers: %d\n",
                accumulate(usedRivers.begin(), usedRivers.end(), 0));
            fprintf(stderr, "  >> num cells: %d\n", usedCells);
        }
    }

    for (int river = 0; river < numRivers; river++) {
        vector <Cell> path = getPath(river);
        fprintf(out, "%d", (int)path.size());
        for (int i = 0; i < (int)path.size(); i++)
            fprintf(out, " %d %d", path[i].row, path[i].col);
        fprintf(out, "\n");
    }
    fclose(out);
}

int main(void) {
    srand(42);
    sTime = clock();
    
    readInput();
    getIntersections();

    greedyByLength();
    greedyByIntersections();
    greedyByIntersectionsRandomized();
    improve(answerOrder);
    randomOrders();
    improve(answerOrder);

    writeOutput();
    
    return 0;