法珞有一个可爱的妹妹露娜，童年的时候两姐妹一起在小山村里幸福地生活着。
在露娜十四岁的时候，法珞留在小山村里教书而露娜走出大山去读高中，两个人就被大山分隔开了呢，只能在山的两侧各自写下自己的思念------
维护一个字符串 $S$ ，支持两种操作：
push-front c执行 $S:=c+S$push-back c执行 $S:=S+c$
在每次操作后，输出 $S$ 本质不同的子串个数。
输入格式
第一行两个整数 $n\ type$ ，表示操作个数和是否强制在线。
接下来的 $n$ 行，每行形如：
push-back ch（ch是小写字母)push-front ch（ch是小写字母)
如果 $type=1$ ，请执行 $ch := (ch - 'a' + lastans) \bmod 26 + 'a'$ 来获得真正的字符。
输出格式
在每次操作后，输出一个整数表示本质不同的子串个数。
样例数据
样例 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): 无其他限制。