Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: bokstai.in

Rezultatų failas: bokstai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Bokštų dėliojimas

Norime n\\timesn dydžio šachmatų lentoje išdėlioti n bokštų pagal tokias taisykles:

  • i-asis bokštas gali būti padėtas stačiakampyje, kurio kampai yra (xl_i; yl_i) ir (xr_i; yr_i), t.y. bokštas gali būti padėtas langelyje (x; y), jei xl_i\\lex\\lexr_i ir yl_i\\ley\\leyr_i.
  • Bokštai vienas kito nekerta, t.y. kiekvienoje eilutėje ir kiekviename stulpelyje yra po vieną bokštą.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n (1\\len\\le5000). Kitose n eilučių yra po keturis sveikuosius skaičius. i-ojoje eilutėje yra xl_i, yl_i, xr_i, yr_i (1\\lexl_i\\lexr_i\\len, 1\\leyl_i\\leyr_i\\len).

Rezultatai

Jei yra bent vienas galimas išdėstymas, išspausdinkite n eilučių, i-ojoje eilutėje rašykite tarpu atskirtas i-ojo bokšto x ir y koordinates. Tinka bet kuris teisingas išdėstymas. Priešingu atveju rašykite "NEPAVYKS" (be kabučių).

Pavyzdys

Duomenys Rezultatai 
8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8
 
1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7