法珞有一个可爱的妹妹露娜,童年的时候两姐妹一起在小山村里幸福地生活着。
在露娜十四岁的时候,法珞留在小山村里教书而露娜走出大山去读高中,两个人就被大山分隔开了呢,只能在山的两侧各自写下自己的思念------
维护一个字符串 S ,支持两种操作:
push-front c
执行 S:=c+Spush-back c
执行 S:=S+c
在每次操作后,输出 S 本质不同的子串个数。
输入格式
第一行两个整数 n type ,表示操作个数和是否强制在线。
接下来的 n 行,每行形如:
push-back ch
(ch
是小写字母)push-front ch
(ch
是小写字母)
如果 type=1 ,请执行 ch:=(ch−′a′+lastans)mod 来获得真正的字符。
输出格式
在每次操作后,输出一个整数表示本质不同的子串个数。
样例数据
样例 1 输入
7 0
push-back b
push-back a
push-front b
push-front a
push-back b
push-front a
push-back d
样例 1 输出
1
3
5
8
11
16
23
样例 2 输入
18 0
push-back c
push-front s
push-back l
push-back o
push-front y
push-front a
push-front w
push-back s
push-back e
push-front l
push-back t
push-back o
push-front a
push-back y
push-back o
push-front m
push-front i
push-back u
样例 2 输出
1
3
6
10
15
21
28
35
44
53
64
75
87
100
114
130
147
165
子任务
对于所有数据 1\leq n\leq 2\times 10^5 。
Subtask 1(20 pts): n\leq 2\times 10^3, type=0
Subtask 2(30 pts): 数据是随机生成的(先按照各 1/2 的概率选择 push-front/push-back ,然后以各 1/26 的概率来选择是哪个小写字母),且 type=0 。
Subtask 3(30 pts): type=0
Subtask 4(20 pts): 无其他限制。