G. Nikita @ Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014 @ Timus Online Judge

G. Nikita

Time limit: 3.0 second
Memory limit: 64 MB

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