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 105.
On the second line, you are given an integer m (1 ≤ m ≤ 105) 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