Faro has a lovely younger sister, Luna. During their childhood, the two sisters lived happily together in a small mountain village.

When Luna turned fourteen, Faro stayed in the village to teach, while Luna left the mountains to attend high school. The two were separated by the mountains, and they could only write down their longing for each other on opposite sides of the mountain.

Maintain a string $S$ and support two types of operations:

1. push-front c: Perform $S := c + S$
2. push-back c: Perform $S := S + c$

After each operation, output the number of distinct substrings of $S$.

Input

The first line contains two integers $n$ and $type$, representing the number of operations and whether the input is encrypted (online).

The next $n$ lines are each in the form:

• push-back ch (ch is a lowercase letter)
• push-front ch (ch is a lowercase letter)

If $type = 1$, perform $ch := (ch - 'a' + lastans) \bmod 26 + 'a'$ to obtain the actual character, where $lastans$ is the answer to the previous operation (initially $0$).

Output

After each operation, output an integer representing the number of distinct substrings of $S$.

Examples

Input 1

7 0
push-back b
push-back a
push-front b
push-front a
push-back b
push-front a
push-back d

Output 1

1
3
5
8
11
16
23

Input 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

Output 2

1
3
6
10
15
21
28
35
44
53
64
75
87
100
114
130
147
165

Subtasks

For all data, $1 \leq n \leq 2 \times 10^5$.

Subtask 1 (20 pts): $n \leq 2 \times 10^3, type = 0$

Subtask 2 (30 pts): The data is randomly generated (choose push-front/push-back with probability $1/2$ each, and choose the lowercase letter with probability $1/26$ each), and $type = 0$.

Subtask 3 (30 pts): $type = 0$

Subtask 4 (20 pts): No additional restrictions.