法珞有一个可爱的妹妹露娜，童年的时候两姐妹一起在小山村里幸福地生活着。

在露娜十四岁的时候，法珞留在小山村里教书而露娜走出大山去读高中，两个人就被大山分隔开了呢，只能在山的两侧各自写下自己的思念------

维护一个字符串 $S$ ，支持两种操作：

1. push-front c 执行 $S:=c+S$
2. 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): 无其他限制。