温馨提示

请注意输入输出对程序效率的影响。

题目描述

坎格鲁斯普雷给了你一个长度为 $n$ 的只包含小写字母的字符串 $s$ ，且保证每种小写字母在 $s$ 中出现至多一次。

坎格鲁斯普雷又给了你一个长度为 $m$ 的只包含小写字母的字符串 $t$ 。

定义 hide 字符串为无限个 $s$ 字符串拼接成的字符串的某一子串，例如，假如 $s=abd$ ，那么 $b$ , $da$ , $bdabda$ 就属于 hide 字符串。

现在，坎格鲁斯普雷将对字符串 $t$ 进行 $q$ 次操作：

1、单点修改某一字符；

2、询问 $[l,r]$ 区间内最长的 hide 字符串的长度。

对于每个操作 $2$ ，你都要回答坎格鲁斯普雷的询问。若区间内没有 hide 字符串，输出 $0$ 。

输入格式

输入第一行三个整数 $n$ , $m$ , $q$ 。 $(1 \leq n \leq 26,1 \leq m,q \leq 5 \times 10^5)$

接下来一行，一个只包含小写字母的字符串 $s$ ，保证每种小写字母在 $s$ 中出现至多一次。

接下来一行，一个只包含小写字母的字符串 $t$ 。

接下来 $q$ 行，先一个整数 $op$ ,表示操作类型。若 $op=1$ ，则接下来一个整数 $p$ 和一个字符 $c$ ，表示将第 $p$ 个字符修改成 $c$ ，保证 $c$ 一定为小写字母；若 $op=2$ ，则接下来两个整数 $l$ , $r$ ，表示询问 $[l,r]$ 区间内最长的 hide 字符串的长度。$(op \in \{1,2\},1 \leq p,l,r \leq m,l \leq r)$

输出格式

对于每个操作 $2$ ，输出一行一个整数表示答案。若区间内没有 hide 字符串，输出 $0$ 。

输入输出样例

输入 #1

3 10 9
abc
babcabdcaa
2 7 7
2 7 10
2 1 10
2 6 9
1 7 c
1 8 b
2 7 10
2 1 10
2 10 10

输出 #1

0
2
5
2
1
6
1

说明与提示

对于样例 #1:

对于第一个询问， $[7,7]$ 区间构成的字符串是 $d$ ，其中没有 hide 字符串。

对于第二个询问， $[7,10]$ 区间构成的字符串是 $dcaa$ ，其中最长的 hide 字符串是 $ca$ 。

对于第三个询问， $[1,10]$ 区间构成的字符串是 $babcabdcaa$ ，其中最长的 hide 字符串是 $abcab$ 。

对于第四个询问， $[6,9]$ 区间构成的字符串是 $bdca$ ，其中最长的 hide 字符串是 $ca$ 。

对于第七个询问， $[7,10]$ 区间构成的字符串是 $cbaa$ ，其中最长的 hide 字符串是 $a$ , $b$ , $c$ 。

对于第八个询问， $[1,10]$ 区间构成的字符串是 $babcabcbaa$ ，其中最长的 hide 字符串是 $abcabc$ 。

对于第九个询问， $[10,10]$ 区间构成的字符串是 $a$ ，其中最长的 hide 字符串是 $a$ 。