Contest problemset description

W pewnym magicznym królestwie słów i liczb żył młody bibliotekarz Bajtazar, którego zadaniem było rozwiązywanie zagadek zapisanych w pradawnych księgach. W tej krainie panowała osobliwa magia: litery wewnątrz słowa mogły być dowolnie poprzestawiane, a mimo to każdy bez trudu je odczytywał – wystarczyło, by pierwsza i ostatnia litera pozostały na swoim miejscu.

Podobna zasada dotyczyła ciągów liczbowych. Mówiła ona, że ciąg liczb całkowitych jest czytelny wtedy, gdy jego pierwszy element jest najmniejszy w całym ciągu, a ostatni – największy. W przeciwnym razie ciąg uznaje się za nieczytelny. Na przykład ciągi [1,3,2,4] i [1,2,1,2] są czytelne, a [1,3,2] i [2,1,2] nie są.

Bajtazar odkrył jednak sposób na odczytywanie ciągów nieczytelnych. Najpierw dzieli cały ciąg liczbowy na czytelne fragmenty, następnie odczytuje każdy z nich, a potem łączy uzyskane informacje w spójną całość. Oczywiście im mniej fragmentów trzeba połączyć, tym łatwiej. Pomóż Bajtazarowi rozszyfrować treść proroctwa i napisz program, który wczyta ciąg liczbowy oraz wypisze najmniejszą liczbę czytelnych fragmentów, na jaką można go podzielić.

Wejście

W pierwszym wierszu znajduje się jedna liczba całkowita N. W drugim i ostatnim wierszu wejścia znajduje się N liczb całkowitych a_i pooddzielanych pojedynczymi odstępami i oznaczających kolejne wyrazy ciągu.

Wyjście

Twój program powinien wypisać tylko jedną liczbę całkowitą – najmniejszą liczbę czytelnych fragmentów, na jaką trzeba podzielić ciąg a_i.

Ograniczenia

1 ≤ N ≤ 300 000, 1 ≤ a_i ≤ 10⁹.

Podzadania

Przykład

6
2 3 1 1 5 1

3

5
5 4 3 2 1

5

4
1 3 2 4

1

Grzybiarz z Kujaw uprawia pieczarki na prostokątnym polu. Pole ma N rzędów i M kolumn. Rzędy numerowane są od 1 do N od góry do dołu. Kolumny numerowane są od 1 do M od lewej do prawej. Niech (r,k) oznacza komórkę w r-tym rzędzie i k-tej kolumnie.

W każdej komórce rośnie pieczarka. Z racji tego, że są one magiczne, to każda ma swój unikalny kolor, reprezentowany numerem od 0 do N × M − 1. Na początku w komórce (i,j) rośnie pieczarka w kolorze A_i, j.

Grzybiarz może przeprowadzać różne operacje na swoim polu. Łącznie zrobi ich Q. Operacje są następujących typów:

• 1 R₁ C₁ R₂ C₂ – zamiana miejscami pieczarek w komórkach (R₁,C₁) i (R₂,C₂).
• 2 W – każda pieczarka zmienia kolor z x na (x+W) mod (N⋅M).
• 3 R₁ C₁ R₂ C₂ – Grzybiarz pyta: jaki jest najmniejszy numer koloru, który nie występuje w żadnej komórce (r,k) która spełnia R₁ ≤ r ≤ R₂ i C₁ ≤ k ≤ C₂? Jeśli wszystkie kolory występują, wypisz -1.

Wejście

Pierwsza linia zawiera dwie liczby całkowite N i M – wymiary pola. Kolejne N linii zawierają po M liczb całkowitych – początkowe kolory pieczarek. Następna linia zawiera liczbę Q – liczbę zdarzeń. Kolejne Q linii opisują zdarzenia w formacie opisanym wyżej.

Wyjście

Dla każdego zdarzenia typu 3 wypisz w osobnej linii najmniejszy numer koloru, który nie występuje w zadanym prostokącie, lub -1, jeśli wszystkie kolory w nim występują.

Ograniczenia

1 ≤ N, M ≤ 500, 0 ≤ A_i, j ≤ N ⋅ M − 1, 1 ≤ Q ≤ 100 000.

Każda liczba od 0 do N ⋅ M − 1 występuje dokładnie raz w początkowej konfiguracji.

Dla zdarzenia typu 1: 1 ≤ R₁, R₂ ≤ N, 1 ≤ C₁, C₂ ≤ M.

Dla zdarzenia typu 2: 1 ≤ W ≤ N ⋅ M − 1.

Dla zdarzenia typu 3: 1 ≤ R₁ ≤ R₂ ≤ N, 1 ≤ C₁ ≤ C₂ ≤ M.

Jest przynajmniej jedno zdarzenie typu 3.

Podzadania

Przykład

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

3
4
-1
0

Po posprzątaniu swojego pokoju, Jasiu postanowił ułożyć swoje maskotki w kolejności tego, jak bardzo je lubi. Zmiany będzie dokonywał poprzez przestawienie maskotek na swojej półce.

Pojawił się jednak problem: Jeśli Jasiu zamieni dwie maskotki miejscami, to od razu będzie widać, że jedną faworyzuje i tej drugiej zrobi się smutno. Postanowił on zatem posłużyć się podstępem – zamiast zamieniać miejscami dwie maskotki, będzie obracał cyklicznie trzy maskotki. Oznacza to, że jeśli są trzy parami różne maskotki A, B i C, to może tak zrobić, żeby A stała na starej pozycji B, B na starej pozycji C, a C na starej pozycji A. Pozycje innych maskotek nie ulegają zmianie.

Ponieważ każda maskotka jest inna, Jasiu przypisał każdej z nich unikalną liczbę w_i oznaczającą, jak bardzo lubi daną maskotkę. Pomóż mu i powiedz, czy za pomocą wyżej opisanego podstępu jest w stanie ustawić maskotki w kolejności malejącej po poziomie lubienia, a jeżeli tak to powiedz mu, ile oraz jakie podstępy musi wykonać.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę maskotek Jasia. W następnym wierszu znajduje się N liczb w_i oznaczających wartości maskotek. Liczby te są parami różne.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK lub NIE, oznaczające odpowiednio, że Jasiu może lub nie może za pomocą jakiejś liczby podstępów ustawić maskotki w zadanej kolejności. Jeżeli odpowiedź brzmi TAK, to w drugim wierszu wyjścia powinna być jedna liczba całkowita K, oznaczająca minimalną liczbę podstępów koniecznych, aby uporządkować jego maskotki na półce. W kolejnych K wierszach powinny widnieć trójki liczb a_i, b_i oraz c_i, oznaczające pozycje maskotek A, B i C w i-tym podstępie. Pozycje liczymy od 1. Jeżeli odpowiedź brzmi NIE, to na wyjściu nie powinno być kolejnych wierszy.

Ograniczenia

1 ≤ N ≤ 10⁶,  − 10⁹ ≤ w_i ≤ 10⁹, 0 ≤ K ≤ 5 ⋅ 10⁶.

Podzadania

Rozwiązania częściowe mogą otrzymać różną część punktów na różnych podzadaniach:

• Za rozwiązanie wypisujące wyłącznie pierwszy wiersz poprawnie przyznawane będzie 10% punktów.
• Za rozwiązanie wypisujące pierwsze dwa wiersze poprawnie z optymalną wartością K przyznawane będzie 30% punktów.
• Za rozwiązanie wypisujące poprawne wyjście z nieoptymalną wartością K, która spełnia warunek K ≤ 4 ⋅ N + 1 000 przyznawane będzie 50% punktów.

Rozwiązanie zawsze powinno wypisać poprawny ciąg operacji, choć niekoniecznie taki, który sortuje wejście.

Przykład

6
67 1 100 -67 -100 -1

TAK
2
1 2 3
4 5 6

2
1 2

NIE

4
1 4 2 3

TAK
1
1 4 2