De ziua lui, Florin a primit un șir de caractere periodic și infinit. Perioada lui are lungime n și conține doar litere mici ale alfabetului englez. Deoarece este curios, el vrea să își personalizeze șirul primit în diverse moduri. Pentru a face asta, el vă dă q operații care se realizează pe șirul dat, operații de două tipuri, după cum urmează:

• 1 x y: Litera de pe poziția x devine egală cu y, unde y este o literă mică a alfabetului englez.
• 2 a b c: Florin vrea să afle câte litere egale cu c există între pozițiile [a, b] din șirul de caractere.

Fiindcă nu vrea să strice periodicitatea șirului foarte mult, Florin vă garantează că pentru toate operațiile de actualizare, valorile pozițiilor modificate au în reprezentarea binară cel mult k biți egali cu 1.

Cerința

Scrieţi un program care, dându-se șirul de caractere și actualizările, răspunde la interogări.

Date de intrare

Fișierul de intrare perioade.in conține pe prima linie n și k, reprezentând lungimea perioadei șirului de caractere, respectiv numărul maxim de biți de 1 pe care îl are o poziție modificată la operația de tipul 1. Pe cea de-a doua linie se va citi perioada șirului de caractere inițial. Pe cea de-a treia linie se va citi q, reprezentând numărul de operații făcut de Florin. Pe următoarele q linii se vor citi operațiile, care respectă descrierea din enunț.

Date de ieșire

Fișierul de ieșire perioade.out va conține răspunsurile pentru operațiile de tipul 2, câte un răspuns pe fiecare linie, în ordinea în care sunt date în datele de intrare.

Restricții și precizări

• 1 ≤ n, q ≤ 250.000
• 1 ≤ k ≤ 4
• Pentru toate query-urile, 1 ≤ x, a, b ≤ 1018, a ≤ b. Pozițiile modificate au cel mult k biți egali cu 1.
• Datorită dimensiunilor mari, numai unele teste au fost adăugate.

Exemplu:

perioade.in

3 4
bun
11
1 9 a
1 7 a
2 3 11 n
1 4 x
2 7 13 b
1 6 o
1 12 b
1 8 r
2 1 15 u
1 7 b
2 3 12 b

perioade.out

2
2
4
3

Explicație

Înainte de operații, șirul este bunbunbunbunbunbun...
După primele două actualizări, șirul devine bunbunauabunbunbun...
Pentru prima operație de tipul 2, avem litera n pe pozițiile 3 și 6.
După următoarea actualizare, șirul devine bunxunauabunbunbun...
Pentru cea de-a doua operație de tipul 2, vom avea litera b pe pozițiile 10 și 13.
După următoarele trei actualizări, șirul devine bunxuoarabubbunbun...
Pentru cea de-a treia operație de tipul 2, vom avea litera u pe pozițiile 2, 5, 11 și 14.
După următoarea actualizare, șirul devine bunxuobrabubbunbun...
Pentru ultima operație de tipul 2, vom avea litera b pe pozițiile 7, 10 și 12.