Układanka

Limit pamięci: 32 MB

Król Bajtazar na swe 145. urodziny otrzymał prezent - ogromną układankę. Układanka ta ma postać tablicy o wymiarach . Pole w -tym rzędzie i -tej kolumnie () ma współrzędne i zawiera element o numerze , . Każdy numer z przedziału jest umieszczony na dokładnie jednym elemencie układanki.

Współrzędne elementów układanki

W celu ułożenia układanki, należy poprzestawiać jej elementy w taki sposób, aby dla każdej pary liczb na pozycji znajdował się element z numerem .

Podczas układania układanki dopuszczalne są następujące ruchy:

• cykliczne przesunięcie elementów w rzędzie w prawo o określoną liczbę pól,
• cykliczne przesunięcie elementów w kolumnie w dół o określoną liczbę pól.

Królowi Bajtazarowi udało się ułożyć układankę, ale nie jest pewien, czy byłby w stanie rozwiązać to zadanie, rozpoczynając od innej konfiguracji początkowej. Pomóź mu rozwiązać ten problem.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis początkowej konfiguracji układanki;
• sprawdzi, czy można poprzekładać elementy układanki, doprowadzając do konfiguracji końcowej, używając tylko i wyłącznie ruchów opisanych powyżej (jeśli da się ułożyć układankę, program powinien znaleźć ruchy, jakie należy wykonać, aby ją ułożyć);
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita - długość boku układanki (). Kolejne wierszy zawiera opis początkowej konfiguracji elementów układanki. -szy wiersz wejścia zawiera liczb całkowitych oddzielonych pojedynczymi odstępami.

Wyjście

Jeśli nie jest możliwe ułożenie układanki, program powinien wypisać na standardowe wyjście tylko jeden wiersz zawierający jedno słowo NO.

Jeśli układankę da się ułożyć, pierwszy wiersz powinien zawierać liczbę - liczbę ruchów prowadzących do ułożenia układanki. Liczba ruchów w Twoim rozwiązaniu nie może przekroczyć . Kolejne wierszy powinno zawierać opisy kolejnych ruchów, jeden ruch na wiersz.

Opis ruchu składa się z litery R (dla cyklicznego przesunięcia wiersza w prawo) lub C (dla cyklicznego przesunięcia kolumny w dół), odstępu, a następnie dwóch liczb oraz oddzielonych pojedynczym odstępem; , . Wiersz zawierający R opisuje cykliczne przesunięcie -tego wiersza o pól w prawo. Taki ruch prowadzi do następującej konfiguracji:

• dla oraz
• dla oraz
• dla

Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać którekolwiek z nich.

Przykład

Dla danych wejściowych:

4
4 6 2 3
5 10 7 8
9 14 11 12
13 1 15 16

poprawną odpowiedzią jest:

2
C 2 1
R 1 3

Powyższa sekwencja ruchów prowadzi do następujących konfiguracji:

Autor zadania: Rafał Rusin.