Klasiskās mediānas

Matemātiķis Krišjānis jau labu laiku aplūko īpaši skaistu matemātisku jēdzienu - mediāna. Mediānu patvaļīgā skaitļu virknē aprēķina šādi:

• Vispirms sakārto virknes elementus augošā secībā un tad:
  • ja elementu skaits ir nepāra skaitlis, tad mediāna ir skaitļu virknes vidējais elements.
  • ja elementu skaits ir pāra skaitlis, tad mediāna ir divu vidējo elementu vidējā vērtība (vidējos elementus saskaita un summu izdala ar 2).

Reiz šis jēdziens lika Krišjānim apsēsties un pārdomāt, kā mediānas varētu visefektīvāk pielietot. Viņš vispirms uz lapas uzrakstīja $N$ veselus skaitļus $a_1, a_2, \ldots, a_N$. Tālāk viņš izdomāja apstrādāt šos skaitļus ar $V$ šāda veida vaicājumiem:

• A tipa vaicājumi - dots indekss $i$ un skaitlis $x$. Ir jānodzēš skaitlis pozīcijā $i$ un tajā pašā vietā jāieraksta skaitlis $x$.

• B tipa vaicājumi - doti indeksi $l$ un $r$. Nepieciešams noskaidrot, kāda ir skaitļu virknes $a_l, \ldots, a_r$ mediāna. Krišjāņa kalkulatoram ir salūzusi dalīšanas poga, tāpēc vaicājumos būs tikai tādi $l$ un $r$, ka $(r - l + 1)$ ir nepāra skaitlis.

Ātri vien Krišjānis saprata, ka šādas darbības veikt uz papīra ir lēni un neefektīvi, tāpēc uzrakstiet datorprogrammu, kas dotām $N, V$ un $a_1, a_2 \ldots a_N$ vērtībām atrod atbildes uz visiem vaicājumiem!

Pirmajā rindā doti divi naturāli skaitļi - elementu skaits virknē $N$ un vaicājumu skaits $V$ $(1 \leq N, V \leq 2 \cdot 10^5)$. Nākamajā rindā ir doti $N$ skaitļi - $a_1, a_2, \ldots, a_N$ $(1 \leq a_i \leq 10^9)$. Nākamajās $V$ rindās ir doti vaicājumi. Vaicājuma rindas sākumā ir dots burts $t \in \{A, B\}$ - vaicājuma tips, aiz kura seko tukšumsimbols. Aiz tukšumsimbola:

• Ja $t = A$, tad šajā rindā sekos divi skaitļi $i$ $(1 \leq i \leq N)$ un $x$ $(1 \leq x \leq 10^9)$. Tas nozīmē, ka skaitlis pozīcijā $i$ ir jānomaina ar skaitli $x$.
• Ja $t = B$, tad šajā rindā sekos divi skaitļi $l$ un $r$ $(1 \leq l \leq r \leq N)$. Tas nozīmē, ka ir nepieciešams atrast skaitļu $a_l, a_{l + 1}, \ldots, a_r$ mediānu. Ir garantēts, ka $(r - l + 1)$ ir nepāra skaitlis.

Zināms, ka ievaddatos būs vismaz viens $B$ tipa vaicājums.

Izvaddatu rindu skaitam jāsakrīt ar $B$ tipa vaicājumu skaitu ievaddatos. Izvaddatu $i$-tajā rindā jāizvada atbilde uz pēc kārtas $i$-to $B$ tipa vaicājumu.