测试数据来自 system/1888

背景

灰色的天空绵绵的细雨
城市里雨雾弥漫
…
没有人懂得的我
就在这里等你啊
——雨のmusique

描述

Al Fine.
最后的《雨のmusique》也要结束了。
就要离开这个充满伤痛的回忆的地方了么……Falsita 的错么……
厚重的伤痛，深深地烙印在眼前，那不公的命运，使最后的梦也化为幻灭。
D.C.
就从这里，脚下的海，来了。
这一切，都结束了。
Fine.
现在给你Fine 最后的乐章（一个字符串S ），要求你回答最后的几个问题。

格式

输入格式

输入共M + 1 行。
第一行一个由小写字母组成的字符串S 和一个整数M ，表示乐章和操作的个数。
接下来的M 行，格式如下：
1 x c type 在T 的某一个串Tx 的前面或后面添加一个字符c ，加入T（Tx不变）。type = 0 表示在末尾，type = 1 表示在开头，其中sz = |T|。
2 x l r 表示询问Tx 在S[l...r] 中的出现次数（下标从1 开始）。
操作1 共有M1 个，操作2 有M2 个，T 是一个字符串集合。

输出格式

输出共M2 行。
对于每个操作2 。输出答案。

样例1

样例输入1

aababdd 5
1 0 b 0
1 1 a 1
2 2 2 5
1 1 d 0
2 3 3 5

样例输出1

2
0

限制

对于10% 的数据1 <= |S|, M <= 2000。
对于另外50% 的数据，type = 0。
对于100% 的数据1 <= |S| <= 90000; 1 <= M <= 200000。
时限每点 2s 。

提示

T1 = b
T2 = ab
Query: S[2...5] = abab
T3 = bd
Query: S[3...5] = bab

来源

Disillusioning #1 水题+原题赛