#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

const int side = 200;
const int size = 10 * 1000;

bool used[side][side], fl[side];
int xc[size], yc[size], cor[size], len;

vector <int> rs;

int tp, n, m, p, k;

void output_test()
{
    int i, s, f;

    for (i = 0; i < 5 * k; i++)
    {
        s = rand() % k;
        f = rand() % k;
        swap(xc[s], xc[f]);
        swap(yc[s], yc[f]);
    }

    printf("%d %d %d %d\n", n, m, p, k);
    for (i = 0; i < p; i++)
    {
        printf("%d", cor[i]);
        i < p - 1 ? printf(" ") : printf("\n");
    }
    for (i = 0; i < k; i++)
        printf("%d %d\n", xc[i], yc[i]);
}

void random_sizes()
{
    int sum = 0, i;

    for (i = 0; i < p; i++)
    {
        rs.push_back(rand() % (min(n / 2, k - sum)));
        sum += rs[i];
    }
    while (sum++ < k)
        rs[rand() % p]++;

    random_shuffle(rs.begin(), rs.end());
}

void gen_path(int ps, int cnt)
{
    int i, px, py;
    py = cor[ps];
    px = 2;
    if (py == 1 || ((rand() % 2) && py != m))
        py++;
    else
        py--;
    for (i = 0; i < cnt; i++)
    {
        if (n - px + 1 - cnt + i > 10 && rand() % 2)
            px++;
        while (used[px][py])
            px++;
        used[px][py] = true;
        xc[len] = px;
        yc[len] = py;
        len++;
        px++;
        if (py == 1 || ((rand() % 2) && py != m))
            py++;
        else
            py--;

    }
}

int main(int argc, char ** argv)
{
    int i, j, ps;

    len = 0;

    tp = atoi(argv[1]);
    n = atoi(argv[2]);
    m = atoi(argv[3]);
    p = atoi(argv[4]);
    k = atoi(argv[5]);
    srand(atoi(argv[6]));

    if (tp == 1)
    {
        for (i = 0; i < p; i++)
        {
            ps = rand() % m + 1;
            while (fl[ps])
                ps = rand() % m + 1;
            fl[ps] = true;
            cor[i] = ps;
            used[1][ps] = true;
        }
        random_sizes();
        for (i = 0; i < p; i++)
            fprintf(stderr, "%d\n", rs[i]);
        for (i = 0; i < p; i++)
            gen_path(i, rs[i]);
        fprintf(stderr,"here\n");
        output_test();
    }

    if (tp == 2)
    {
        int help = min(10, k / 3);
        k -= help;
        for (i = 0; i < p; i++)
        {
            ps = rand() % m + 1;
            while (fl[ps])
                ps = rand() % m + 1;
            fl[ps] = true;
            cor[i] = ps;
            used[1][ps] = true;
        }
        random_sizes();
        //for (i = 0; i < p; i++)
        //    fprintf(stderr, "%d\n", rs[i]);
        for (i = 0; i < p; i++)
            gen_path(i, rs[i]);
        k += help;
        ps = rand() % m + 1;
        for (i = n; i > 1; i--)
            if (!used[i][ps] && help > 0)
            {
                used[i][ps] = true;
                xc[len] = i;
                yc[len] = ps;
                len++;
                help--;
            }
        output_test();
    }
}
