Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este “Nu poate să rămână decât unul singur”. Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) se află maxim n•m-1 nemuritori. Doi nemuritori vecini se “luptă” între ei şi cel care pierde lupta este eliminat. “Lupta” constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j) înţelegem un nemuritor din una dintre poziţiile (i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j) se va găsi în una dintre poziţiile: (i-2,j), (i+2,j), (i,j-2) sau (i,j+2), dacă această poziţie este liberă şi este în interiorul zonei.

Cerinţă

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

Date de intrare

Fișierul de intrare immortal.in conține pe prima linie trei valori naturale n m I, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane ale zonei descrise şi respectiv numărul de nemuritori existenţi iniţial. Următoarele I linii conţin fiecare câte două numere naturale x y separate printr-un spaţiu, reprezentând poziţiile unde se găsesc iniţial cei I nemuritori (linia şi coloana).

Date de ieșire

Fișierul de ieșire immortal.out va conține I-1 linii, fiecare linie descriind o “luptă”. Luptele vor fi scrise în ordinea în care au avut loc. O linie va conţine 4 numere naturale care indică: primele două poziţia de pe care pleacă un nemuritor la “luptă”, ultimele două poziţia pe care acesta ajunge după “luptă”. Pentru ca “lupta” să fie corectă, în poziţia peste care nemuritorul “sare” trebuie să existe un nemuritor care va “muri”. O poziţie va fi specificată prin indicele de linie urmat de indicele de coloană. Valorile scrise pe aceeaşi linie vor fi separate prin spaţii.

Restricții și precizări

• 1 < n, m ≤ 20
• 1 < I ≤ min{15, n*m-1}
• Pentru datele de test există întotdeauna soluţie.

Exemplu

immortal.in

3 4 4
1 2
2 1
3 2
3 3

immortal.out

3 3 3 1
3 1 1 1
1 1 1 3

Explicație

  1   2   3   4
 =================    (3,3) --> (3,1)  dispare (3,2)
1|   | * |   |   |    (3,1) --> (1,1)  dispare (2,1)
 |---------------|    (1,1) --> (1,3)  dispare (1,2)
2| * |   |   |   |
 |---------------|
3|   | * | * |   |
 =================

#include <bits/stdc++.h>


using namespace std;

ifstream cin ("immortal.in");
ofstream cout ("immortal.out");

const int di[] = {1, 0, -1, 0};
const int dj[] = {0, 1, 0, -1};

const int di2[] = {2, 0, -2, 0};
const int dj2[] = {0, 2, 0, -2};

int n, m, nrf;
bool mort[500], ok;
int a[21][21];

vector< pair<int, int> > fr;

struct patru
{
    int a, b, c, d;
}rasp[500];

void afis();
void back(int);
bool inside(int, int);

int main()
{
    cin >> n >> m >> nrf;
    fr = vector< pair<int, int> >(nrf + 1);

    for (int i = 1; i <= nrf; i ++)
    {
        cin >> fr[i].first >> fr[i].second;
        a[fr[i].first][fr[i].second] = i;
    }
    back(1);
    return 0;
}
void back(int ind)
{
    if (ok)return;
    if (ind == nrf)
    {
        afis();
        ok = 1;
        return;
    }
    int x, y;
    for (int i = 1; i <= nrf; ++ i)
        if (!mort[i])
        {
            x = fr[i].first;
            y = fr[i].second;
            for (int d = 0, p; d < 4; ++ d)
                if (a[x + di[d]][y + dj[d]] && !a[x + di2[d]][y + dj2[d]] && inside(x + di2[d], y + dj2[d]))
                {
                    p = a[x + di[d]][y + dj[d]];
                    mort[a[x + di[d]][y + dj[d]]] = 1;
                    a[x + di[d]][y + dj[d]] = 0;
                    a[x + di2[d]][y + dj2[d]] = i;
                    a[x][y] = 0;
                    fr[i].first = x + di2[d];
                    fr[i].second = y + dj2[d];

                    rasp[ind].a = x; rasp[ind].b = y;
                    rasp[ind].c = x + di2[d]; rasp[ind].d = y + dj2[d];

                    back(ind + 1);

                    mort[p] = 0;
                    a[x + di[d]][y + dj[d]] = p;
                    a[x + di2[d]][y + dj2[d]] = 0;
                    a[x][y] = i;
                    fr[i].first = x;
                    fr[i].second = y;
                }
        }
}
void afis()
{
    for (int i = 1; i <= nrf - 1; ++ i)
        cout << rasp[i].a << ' ' << rasp[i].b << ' ' << rasp[i].c << ' ' << rasp[i].d << '\n';
}
bool inside(int x, int y)
{
    return x <= n && y <= m && x >= 1 && y >= 1;
}