葫芦和斌斌的字符串2

题号：NC233500
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一个长度为 ${n}$ 的仅包含小写字母的字符串 ${S}$ ，有 $Q$ 次操作：

1. 修改操作： $1\ ch$ 表示向字符串末尾添加一个字符 $ch$

2. 查询操作： $2\ k$ ，求一个最长的字符串 $T$ 满足： ${T}$ 为 ${S}$ 的前缀， ${T}$ 为 ${S}$ 的后缀，且 ${T}$ 在 ${S}$ 中至少出现 $k$ 次

第一行一个整数分别表示初始字符串长度，操作数
第二行为字符串
后面行，每行表示一个操作
,保证 修改操作 中的  为小写英文字母

对于每个查询操作，输出最长的满足条件的的长度，如果没有满足条件的则输出

示例1

复制

6 5
abcabc
2 2
2 3
1 a
1 b
2 3

复制

3
-1
2