Description

给出一个长度为 $N~(N\le 10^5)$ 的字符串 $S$ 和 $Q~(Q\le 10^5)$ 个操作，每个操作都是以下的任意一个 :

• LCP (a, b) : 询问当前字符串 $S$ 中 $S_{a,...,n}$ 和 $S_{b,...,n}$ 的最长公共前缀。保证 $1\le a,b,\le n$ 。
• ADD (a, S2) : 在当前字符串 $S$ 的第 $a$ 个字符前插入字符串 $S2$ ，也就是将 $S$ 变成 $S_{1,...,a-1}+S2+S_{a,...,n}$ 。如果 $a=n+1$ 则在 $S$ 的最后加上 $S2$ 。保证 $1\le a \le n+1$ 。
• CHG (a, b, S2) : 在当前字符串 $S$ 种将 $S_{a,...,b}$ 替换为 $S2$ 。保证 $b-a+1=|S2|,~1\le a\le b\le n$ 。
• DEL (a, b) : 从当前字符串 $S$ 中删去第 $a$ 个字符到 第 $b$ 个字符，也就是将 $S$ 变成 $S_{1,...,a-1}+S_{b+1,...,n}$ 。保证 $1\le a\le b\le n$ 。

保证插入的字符串长度总和、修改的字符串长度总和均不超过 $10^5$ ，ADD,CHG,DEL 的总操作数不超过 $5000$ 个。

Input Format

第一行是两个正整数 $N,Q$ 。

第二行是一个长度为 $N$ 的字符串 $S$ 。

接下来 $Q$ 行，每行描述一个操作，指令种类的输入格式为上述描述指令名称的第一个字符（L 对应 LCP，A 对应 ADD，C 对应 CHG ，D 对应 DEL）。后续的整数和字符串的输入见题目描述。

Output Format

对于每个Lcp(a,b)操作输出最长公共前缀

47
abab
L 13
A 1 ab
L 1 3
C 56 cb
L 1 3
D 1 2
L 1 3

2
4
2
0