Problem description

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