After Nikita failed to solve a problem about queries on a segment at IOI, he decided to please the participants of Petrozavodsk
training camp by another problem of the same nature.
You are given a string s, an integer k and queries.
There are two types of queries:
 For given numbers l and r, fill a substring s[l..r] with character c.
 For given l and r, determine the number of pairs i, j such that l ≤ i ≤ j ≤ r, j − i + 1 ≤ k and s[i..j] is a palindrome.
Characters in the string are numbered starting from one.
Input
The first line contains a string s and an integer k (1 ≤ k ≤ 50). The length of the given string does not exceed 10^{5}.
On the second line, you are given an integer m (1 ≤ m ≤ 10^{5}) which is the number of queries.
Next m lines describe the queries. Each line starts with a query type (1 or 2), then follow integers l, r (1 ≤ l ≤ r ≤ s) and a
lowercase Latin letter c (for type 1 queries only).
Output
For every type 2 query, print an integer on a separate line.
Sample
input  output 

abacaba 4
3
2 1 3
1 1 3 c
2 1 4
 4
10

Problem Author: Nikita Sivukhin
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014