Se dă o matrice cu \(2\) linii și \(N\) coloane. De asemenea, se dau \(Q\) operații de \(2\) tipuri, pe care va trebui să le procesați în ordine. Cele \(2\) tipuri de operații sunt definite astfel:

• \(1\) \(lin\) \(col\) \(x\) – valoarea elementului aflat pe linia \(lin\) și coloana \(col\) va deveni \(x\).
• \(2\) \(st\) \(dr\) – afișați scorul submatricei cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\).

Scorul unei submatrice cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\) este calculat astfel:

1. Se pot permuta oricum coloanele submatricei. (Această permutare nu va persista la următoarele operații.)
2. După pasul anterior, se va alege un drum de lungime minimă cu capetele în celulele \((1,st)\), respectiv \((2,dr)\). Un drum este format dintr-o succesiune de celule distincte, unde oricare două celule consecutive din drum sunt adiacente pe linie sau pe coloană.
3. Scorul submatricei este egal cu valoarea minimă posibilă a medianei numerelor dintr-un drum construit la pasul anterior.

Definim mediana unui șir de numere \(A\) cu \(M\) elemente, numerotate de la \(1\) la \(M\), ca fiind elementul aflat pe poziția \(\lceil\frac{M}{2} \rceil\) în urma sortării șirului. De exemplu, mediana șirului \([1,3,1,2]\) este \(1\), iar mediana șirului \([1,2,3]\) este \(2\).

Cerința

Se cere să se determine scorul submatricei date pentru fiecare operație de tip \(2\).

Date de intrare

Pe prima linie se va afla numărul \(T\), reprezentând numărul de teste.

Pe prima linie a celui de-al \(i\)-lea test se vor afla două numere \(N\) și \(Q\) – numărul de coloane din matrice, respectiv numărul de operații.

Pe a doua linie a celui de-al \(i\)-lea test se vor afla \(N\) numere, reprezentând valorile inițiale ale elementelor de pe prima linie a matricei.

Pe a treia linie a celui de-al \(i\)-lea test se vor afla \(N\) numere, reprezentând valorile inițiale ale elementelor de pe a doua linie a matricei.

Pe următoarele \(Q\) linii ale celui de-al \(i\)-lea test se vor afla descrierile operațiilor, câte un una pe fiecare pe linie. Fiecare dintre următoarele \(Q\) linii va avea unul dintre următoarele formaturi:

• \(1\) \(lin\) \(col\) \(x\)
• \(2\) \(st\) \(dr\).

Toate valorile de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Pentru fiecare operație de tipul \(2\) se va afișa răspunsul pe câte o linie.

Restricții și precizări

• \(1 \leq T \leq 8\)
• \(1 \leq N,Q \leq 10^5\)
• \(1 \leq \text{numerele din matrice} \leq 3 \cdot 10^5\)
• Pentru toate operațiile de tipul \(1\):
  • \(1 \le lin \le 2\), \(1 \le col \le N\)
  • \(1 \le x \le 3 \cdot 10^5\)
• Pentru toate operațiile de tipul \(2\):
  • \(1 \le st \le dr \le N\)

Subtask-uri

Notă: testele sunt grupate în subtask-uri.

Exemplul 1:

Intrare

1
6 7
10 6 9 5 1 6
6 9 10 3 3 1
2 1 6
2 3 3
1 2 4 6
2 1 6
1 2 5 4
1 1 5 9
2 4 6

Ieșire

3
9
5
4

Explicație

Pentru prima operație este optim să permutăm coloanele matricei în următorul mod:

$$\begin{bmatrix}
\textbf{6} & \textbf{9} & \textbf{1} & 5 & 6 & 10 \\
9 & 10 & \textbf{3} & \textbf{3} & \textbf{1} & \textbf{6}
\end{bmatrix}$$

Mediana minimă a unui drum din celula \((1,1)\) în celula \((2,6)\) este \(3\), obținută din drumul conținând celulele cu valorile \([6,9,1,3,3,1,6]\).

Exemplul 2:

Intrare

1
8 9
2 1 2 2 1 1 2 2
1 2 1 2 2 1 2 1
2 1 8
1 1 2 2
2 4 5
2 5 5
1 1 6 2
2 4 7
2 5 8
1 2 3 2
2 1 3

Ieșire

1
2
1
2
1
2

Explicație

Acest test se încadrează în subtask-ul \(3\).

Exemplul 3

Intrare

1
7 6
5 1 4 9 10 3 3
4 1 9 6 5 10 4
2 1 7
2 2 4
2 5 6
2 3 3
2 4 6
2 6 7

Ieșire

3
1
5
4
5
3

Explicație

Acest test se încadrează în subtask-ul \(4\).

Exemplul 4

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

Ieșire

3
9
5
4
1
2
1
2
1
2
3
1
5
4
5
3