În timpul vacanței cu familia Maria a vizitat multe obiective turistice. Ce a impresionat-o cel mai mult a fost un zid imens făcut din pietre. Zidul avea o formă dreptunghiulară și era format din pietre individuale de aceeași înălțime (cu lățimi nu neapărat egale), aranjate pe linii, una deasupra celeilalte. Numărul de pietre din zid era N, ele fiind numerotate cu numere întregi de la 1 la N. Pe fiecare piatră era scris numărul ei de ordine. Maria a constatat că pietrele de pe o linie nu sunt neapărat așezate (de la stânga la dreapta) în ordinea crescătoare a numerelor de ordine.

Ce a impresionat-o și mai tare pe fetiță a fost faptul că marginile dintre pietrele de pe două linii adiacente
nu coincideau, altfel spus, marginile dintre pietre nu sunt exact una deasupra celeilalte. În plus, ea și-a notat într-o listă toate cele M perechi de numere întregi ui și di, astfel încât piatra cu numărul de ordine ui stă pe piatra cu numărul de ordine di. Spunem că o piatră stă pe altă piatră dacă prima piatră se află pe linia imediat deasupra liniei celei de-a doua pietre și latura de jos a primei pietre se suprapune peste latura de sus a celei de-a doua pietre pe un segment de lungime naturală nenulă.

Odată ajunsă acasă, fetița l-a rugat pe tatăl ei să reproducă această capodoperă arhitecturală pe o foaie
mare de hârtie, împărțită în pătrățele unitare, respectând următoarele condiții:

• Numărul de pietre să rămână neschimbat;
• Zidul desenat să fie perfect în forma unui dreptunghi;
• Să nu existe două laturi verticale, pe linii adiacente, fix una deasupra celeilalte;
• Înălțimea fiecărei pietre trebuie sa fie o unitate;
• Lățimea fiecărei pietre poate fi aleasă de către tatăl ei, dar trebuie să fie un număr natural nenul;
• Dacă o piatră se afla, în zidul inițial, peste o altă piatră, acest lucru se va păstra și în reproducere;
• Pentru fiecare pereche de pietre descrisă, latura de jos a pietrei de sus se va suprapune peste latura de
  sus a pietrei de jos pe un segment de lungime naturală nenulă.

Cerința

Scrieți un program care determină dimensiunile dreptunghiului de arie minimă, care să reproducă zidul, conform cerințelor Mariei.

Date de intrare

De pe prima linie a intrării standard se vor citi doi întregi N și M – numărul pietrelor și numărul perechilor din listă. De pe fiecare dintre următoare M linii se vor citi doi întregi ui și di cu semnificația că piatra cu numărul de ordine ui stă pe piatra di. De pe ultima linie se va citi un întreg cu valoare de 0 sau 1. Dacă valoarea respectivă este 1, atunci este garantat că numerele de ordine ale pietrelor de pe fiecare linie erau ordonate crescător, de la stânga la dreapta, în zidul original. Acest lucru nu înseamnă că este necesar ca reproducerea să respecte această proprietate.

Date de ieșire

Pe prima linie a ieșirii standard, se vor afișa doi întregi H și W, reprezentând înălțimea și respectiv lățimea dreptunghiului de arie minimă a reproducerii zidului. Pe fiecare dintre următoarele H linii afișați o descriere a unei posibile aranjări a pietrelor din reproducerea zidului – a i-a astfel de linie va conține un singur număr ki – numărul de pietre de pe a i-a linie a zidului, urmat de ki perechi de întregi reprezentând pietrele de pe linia respectivă, fiecare dată prin numărul de ordine al pietrei respective și lățimea ei în unități. Fiecare două numere consecutive trebuie să fie separate printr-un singur spațiu. Pietrele trebuie afișate pe linii de la cea mai de sus, la cea mai de jos. Dacă există mai multe soluții, poate fi afișată oricare dintre ele.

Restricții și precizări

• 1 ≤ N ≤ 200.000
• În aproximativ 15% dintre teste, 1 ≤ N ≤ 10
• În alte aproximativ 40% dintre teste, numerele pietrelor de pe fiecare rând al zidului original sunt în ordine
  crescătoare de la stânga la dreapta.

Exemplul 1:

Intrare

11 14
1 4
1 8
2 6
4 3
4 11
5 2
5 4
5 7
5 10
7 6
7 11
8 3
9 4
10 6
0

Ieșire

3 8
3 1 2 9 1 5 5
5 8 1 4 3 7 2 10 1 2 1
3 3 2 11 3 6 3

Explicație

Diagrama arată un aranjament posibil al pietrelor în zidul reprodus în cadrul primului exemplu, în care o arie minimă a dreptunghiului reprezentând zidul este obținută, astfel încât toate condițiile impuse sunt respectate.

Exemplul 2:

Intrare

4 3
1 4
2 4
3 4
1

Ieșire

2 3
3 1 1 3 1 2 1
1 4 3