2. Zákerní súrodenci

Alžbetka má malú sestru. Jedného dňa sa Alžbetka rozhodla vyrobiť náhrdelník z korálok. Jej malá sestra pri tom samozrejme nemohla chýbať a musela jej pomôcť. Na začiatku Alžbetka navliekla na šnúrku nejaké korálky. Podľa jej sestry to však spravila úplne zle a teda musí vymeniť túto korálku za novú, a tamtú tiež…¹ Veď poznáte malé sestry.

Alžbetka by bola rada, keby ten náhrdelník vyzeral aspoň trochu dobre. Napríklad aby bol symetrický. Pri všetkom tom vymieňaní korálok by teda chcela vedieť, kedy sa tak stane.

Úloha

Jednotlivé druhy korálok budeme reprezentovať malými písmenami anglickej abecedy a-z. Na začiatku dostanete popis náhrdelníka – nejaký reťazec znakov, ktorý popisuje jednotlivé korálky v náhrdelníku. Postupne v ňom budeme vymieňať korálky za iné. Po každej takejto výmene povedzte, či je daný reťazec symetrický – tj. či sa odzadu číta rovnako ako spredu.

Formát vstupu

V prvom riadku vstupu je reťazec dĺžky \(n\) (\(1 \leq n \leq 100\,000\)) – popis pôvodného náhrdelníka. V druhom riadku je číslo \(q\) (\(1 \leq q \leq 100\,000\)) – počet zmien, ktoré nastanú. Ďalších \(q\) riadkov bude obsahovať medzerou oddelené číslo a znak – pozícia korálky, ktorú treba vymeniť (číslujeme od \(0\)) a druh (písmeno), na ktorý sa má korálka zmeniť.

Formát výstupu

Na výstup vypíšte \(q\) riadkov, pričom každý bude obsahovať buď "ano" alebo "nie" (bez úvodzoviek) podľa toho, či je reťazec po danej zmene symetrický, alebo nie.

Pozor na veľkosť vstupu a výstupu. S pomalým načítavaním/vypisovaním môžete dostať hlášku "TLE - Prekročený časový limit" aj s inak rýchlym riešením.

Príklady

Input:

abcabc
3
0 c
2 a
3 c

Output:

nie
ano
nie

Po prvej zmene bude reťazec vyzerať takto: cbcabc, čo nie je symetrické. Po druhej zmene bude vyzerať takto: cbaabc, čo symetrické je. Treťou zmenou nám to sestra pokazí a reťazec opäť nebude symetrický.

Input:

ppppp
2
2 a
3 p

Output:

ano
ano

Prvou zmenou sme zmenili znak v strede; reťazec ostane symetrický. Druhou zmenou zmeníme p na p; reťazec ostane rovnaký.