Medwalk

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ță

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

Date de intrare

Pe prima linie se vor afla două numere $N$ și $Q$ - numărul de coloane din matrice, respectiv numărul de operații.

Pe a doua linie se vor afla $N$ numere, reprezentând valorile inițiale ale elementelor de pe prima linie a matricei.

Pe a treia linie se vor afla $N$ numere, reprezentând valorile inițiale ale elementelor de pe a doua linie a matricei.

Pe următoarele $Q$ linii 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 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$

Exemplul 1

stdin

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

stdout

3
9
5
4

Explicație

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

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

stdin

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

stdout

1
2
1
2
1
2

Explicație

Acest test se încadrează în subtask-ul $3$.

Exemplul 3

stdin

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

stdout

3
1
5
4
5
3

Explicație

Acest test se încadrează în subtask-ul $4$.