Nosaukums
Gadījuma palindroms (random_palindrom)
Laika limits
1.00s
Atmiņas limits
16.0 MB
Grūtība
41%

Definīcija

Lai aprēķinātu gadījuma vērtību, ir izgudroti dažādi algoritmi, kuri ir piemēroti dažādām situācijām, tie ir balstīti uz dažādiem gadījuma datiem un to efektivitāte ir dažāda. Gudrinieku ciemā ir radusies nepieciešamība pēc šāda algoritma. Ciema zinātnieki ir nosprieduši, ka gadījuma datiem vislabāk atbilst virkne ar instrukcijām, kuras skolotāji sniedz skolēniem pirms sporta spēlēm, lai padarītu komandas neparedzamākas.

Katrs skolnieks ir apzīmēts ar simbolu atkarībā no tā fiziskās sagatavotības (A – Z). Pirmajā rindā ir dotas skolnieku pozīcijas simbolu virknes S garums M un skaitlis N. Otrajā rindā ir dots S. Katrā nākamajā no 1 ≤ N ≤ 106 rindām ir dota instrukcija. Katra instrukcija ir divi skaitļi 1 ≤ a ≤ M, 1 ≤ b ≤ M. Instrukcija nozīmē, ka ir jāapmaina vietām virknes simboli pozīcijās a, b. Zinātnieki vienojās, ka, lai aprēķinātu gadījuma skaitli, ir jāizpilda visas instrukcijas un jāaprēķina, kāda ir iegūtās simbolu virknes līdzība palindromam. Līdzību palindromam aprēķina saskaitot visus S[i], kuri ir vienādi ar S[Mi + 1], kamēr i ≤ Mi + 1 (indeksējot no 1).


Ievaddatu raksturojums

Pirmajā rindā ir doti divi skaitļi, virknes S garums M (1 ≤ M ≤ 105) un instrukciju skaits N (1 ≤ N ≤ 106). Otrajā rindā ir dota simbolu virkne S.
Katrā no nākamajām N rindām ir dota instrukcija a, b (1 ≤ a, b ≤ M).


Izvaddatu raksturojums

Izvaddatos ir jāizvada pēc katras instrukcijas savā rindā viens skaitlis – līdzība palindromam.


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
M, N ≤ 1000 27
Bez papildus ierobežojumiem 23
Kopā:    50

 


Paraugdati

Stdin
5 4
ABABB
1 2
2 1
3 5
2 4
Stdout
2
2
3
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.