在 Nikita 未能在 IOI 上解决一道关于区间查询的问题后，他决定为彼得罗扎沃茨克训练营的参赛者们出另一道同类问题。

给定一个字符串 $s$、一个整数 $k$ 以及若干查询。

查询分为两种类型：

1. 对于给定的数字 $l$ 和 $r$，将子串 $s[l..r]$ 全部填充为字符 $c$。
2. 对于给定的 $l$ 和 $r$，确定满足 $l \le i \le j \le r$、$j - i + 1 \le k$ 且 $s[i..j]$ 是回文串的数对 $(i, j)$ 的数量。

字符串中的字符从 1 开始编号。

输入格式

第一行包含一个字符串 $s$ 和一个整数 $k$ ($1 \le k \le 50$)。给定字符串的长度不超过 $10^5$。第二行给出一个整数 $m$ ($1 \le m \le 10^5$)，表示查询的数量。 接下来的 $m$ 行描述了查询。每行以查询类型（1 或 2）开头，随后是整数 $l, r$ ($1 \le l \le r \le |s|$)，以及一个小写拉丁字母 $c$（仅针对类型 1 查询）。

输出格式

对于每个类型 2 的查询，输出一行一个整数。

样例

样例输入 1

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

样例输出 1

4
10