Szachownica

Limit pamięci: 32 MB

Dana jest szachownica o rozmiarach , gdzie jest nieparzystą liczbą całkowitą spełniającą nierówność , oraz zestaw kostek. Każda kostka ma kształt prostokąta pokrywającego dokładnie dwa pola. Pola szachownicy są ponumerowane kolejno wierszami - pola w pierwszym wierszu (od lewej do prawej) liczbami od do , pola w drugim wierszu od do i tak dalej aż do pola w prawym dolnym rogu, które ma numer .

Z szachownicy wycinamy trzy dowolne pola, a następnie chcemy ją pokryć kostkami, w taki sposób, aby każde nie wycięte pole pokrywała jedna kostka (pokrywająca też jedno z sąsiednich pól), a pola wycięte pozostały nie pokryte.

Czy zawsze jest to możliwe?

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia rozmiar szachownicy oraz trzy numery wyciętych pól szachownicy,
• bada, czy taką szachownicę można pokryć kostkami i jeśli nie, to zapisuje w standardowym wyjściu odpowiedź NIE, a jeśli tak, to zapisuje w standardowym wyjściu ciąg par liczb całkowitych wskazujących ułożenie kostek pokrywające daną szachownicę.

Jeśli istnieje wiele sposobów pokrycia szachownicy kostkami, Twój program powinien wypisywać tylko jeden z nich.

Wejście

W jedynym wierszu standardowego wejścia są zapisane cztery liczby pooddzielane pojedynczymi odstępami. Pierwsza liczba to rozmiar szachownicy , a trzy następne to numery wyciętych pól. Po ostatniej liczbie następuje koniec wiersza.

Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.

Wyjście

Standardowe wyjście powinno zawierać albo jedno słowo NIE, albo w każdym z kolejnych wierszy dwie liczby oddzielone odstępem, to znaczy numery dwóch sąsiednich pól pokrywanych przez jedną kostkę.

Przykłady

Dla danych wejściowych:

7 17 25 40

poprawną odpowiedzią jest:

18 19
20 21
8 9
10 11
12 13
14 7
6 5
4 3
1 2
15 22
16 23
29 36
30 37
24 31
32 39
43 44
38 45
46 47
48 49
41 42
33 34
35 28
26 27

Dla danych wejściowych:

7 25 32 40

poprawną odpowiedzią jest:

NIE

Autor zadania: Wojciech Rytter.