Zadanie

Kruhy

Počet bodov: 75

Koza je veľmi nenažrané zviera. Kozičky, ktoré utiekli zo ZOO, začali jesť vo voľnej prírode všetko, čo im prišlo do cesty. Zanedlho ale nehorázne pribrali a preto sa rozhodli, že príjmu obmedzenia, ktoré tento trend zastaví.

Podobne ako na dedinách po celom svete si kozičky chcú zorganizovať konzumáciu nasledovne. Ráno prídu na lúku. Každá sa priviaže reťazou ku kolíku, ktorý si zapichnú niekde do zeme. Každá kozička sa bude pásť len v kruhovej oblasti, pokiaľ jej reťaz dovolí. Lúka má v tejto úlohe obdĺžnikový tvar a je veľká \(R \times S\) metrov. Každá kozička si pripravila reťaz vhodnej dĺžky podľa toho, ako veľmi chce schudnúť (alebo ako najviac chce pribrať).

Kozičky nechcú bojovať o lúku a preto by sa oblasti ich dosahu nemali pretínať (dotýkať sa môžu). Pomôžte im preto a nájsť správne miesta pre zapichnutie kolíkov tak, aby sa nestalo, že na nejaký kúsok lúky dosiahne viac ako jedna kozička.

Formát vstupu a výstupu

Na prvom riadku vstupu sú tri celé čísla: rozmery lúky \(R, S~(1 \leq R, S \leq 1,000,000,000)\) a počet kozičiek \(N (1 \leq N \leq 50)\). Ľavý horný roh lúky má súradnice \([0,0]\) a pravý dolný roh má súradnice \([R-1, S-1]\).

Na druhom riadku vstupu je \(N\) medzerou oddelených celých čísel: dĺžky reťazí jednotlivých kozičiek. Tieto čísla sú kladné a nepresahujú 1,000,000,000. Môžete predpokladať, že súčet obsahov všetkých kruhov je najviac tretina plochy lúky.

Na výstup vypíšte \(N\) riadkov: celočíselné súradnice kolíkov kozičiek v poradí, v akom idú na vstupe. Kolíky musia byť zapichnuté na lúke alebo jej okraji. Oblasti pridelené kozičkám môžu presahovať hranice lúky. Samozrejme, žiadne dve oblasti sa nesmú prekrývať.

Príklady

Input:

12 12 3
1 3 1

Output:

11 8
11 4
3 5

Všimnite si, že teritórium prvých dvoch kozičiek čiastočne siaha mimo lúku. Okrem toho sa tieto dve teritóriá dotýkajú.

Input:

10047 1 2
30 1

Output:

54 0
1 1