Problem Statement

Rintaro often participates in a virtual contest called "Asakatsu".

In each Asakatsu, $6$ distinct problems are chosen at random from past AtCoder problems (hereafter simply called problems).
Problems are distinguished by their names: problem $P$ and problem $P'$ are the same problem if and only if $P = P'$.
Problem names are given as strings consisting of lowercase English letters.

Rintaro solves the Asakatsu problems in order starting from the $1$st problem, as many as possible within $60$ minutes.

• More precisely, if the $i \ (1 \leq i \leq 6)$-th problem takes $x_i$ minutes to solve,
  he takes the largest positive integer $k$ $(1 \leq k \leq 6)$ satisfying $x_1 + x_2 + \cdots + x_k \leq 60$ and solves up to the $k$-th problem.
  If no such $k$ exists, he does not solve even $1$ problem.

Here, among the problems he has solved so far, Rintaro has a sense of "déjà vu" about the most recent $N$ problems.
If and only if he has déjà vu about a problem $P$ that takes $d$ minutes to solve, he solves problem $P$ in $\min(d, K)$ minutes.
A precise description of "the most recent $N$ problems" is given below.

You are given $Q$ queries. Each query is one of the following $2$ types.

• Query $1$: Solve problem $s$.
• Query $2$: Participate in Asakatsu. The $i \ (1 \leq i \leq 6)$-th problem is problem $t_i$, and it takes $d_i$ minutes to solve.

Process the $Q$ queries as described below.
Also, each time Query $2$ is given, print on $1$ line the number of problems Rintaro solved in that Asakatsu.

• Define $A$ as "the array of problems solved so far", and let $M$ be its number of elements. Initially, $A$ is empty.
• For $i = 1, 2, \dots, Q$ in this order, process the $i$-th query by the following steps.
• For Query $1$
• Append problem $s$ to the end of $A$.
• For Query $2$
• Let $j = \max(1,M-N+1)$ and $B = (A_j, A_{j+1}, \dots, A_M)$ (if $M = 0$, $B$ is empty). Then,
  Rintaro has déjà vu about a problem $P$ if and only if problem $P$ is contained in $B$.
• He solves the Asakatsu problems given in that query in order starting from the $1$st problem.
• After the Asakatsu ends, all the problems solved in that Asakatsu are appended to the end of $A$ in the order they were solved.

Regarding the condition for déjà vu, for example, if $A = ($a, s, a, ka, tsu$)$, the following holds.

• If $N = 1$, then $B = ($tsu$)$.
• If $N = 2$, then $B = ($ka, tsu$)$.
• If $N = 3$, then $B = ($a, ka, tsu$)$.
• If $N = 4$, then $B = ($s, a, ka, tsu$)$.
• If $N = 5$, then $B = ($a, s, a, ka, tsu$)$ (the same applies to $N = 6, 7, \dots$).

Input

$N$ $K$ $Q$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\vdots$
$\mathrm{Query}_Q$

• The $i$-th query $\mathrm{Query}_i \ (1 \leq i \leq Q)$ is given in one of the following formats.
• If the $i$-th query is Query $1$:

  $1$
  $s$
  

• If the $i$-th query is Query $2$:

  $2$
  $t_1$ $d_1$
  $t_2$ $d_2$
  $\vdots$
  $t_6$ $d_6$
  

• All input values other than strings are integers
• $1 \leq N, Q \leq 500$
• $1 \leq K \leq 100$
• $1 \leq d_i \leq 100 \ (1 \leq i \leq 6)$
• $s, t_1, t_2, \dots, t_6$ are strings consisting of lowercase English letters
• $1 \leq |s|, |t_i| \leq 10 \ (1 \leq i \leq 6)$
• In each Query $2$, $t_1, t_2, \dots, t_6$ are distinct

Output

Each time Query $2$ is given, print on $1$ line the number of problems Rintaro solved in that Asakatsu.

Sample

2 10 3
1
xor
1
and
2
bit 5
or 10
and 20
xor 25
rmq 25
hard 60

5

3 5 7
1
abc
1
solve
2
uuu 3
abc 15
solve 20
asakatsu 50
pura 70
contest 100
2
uuu 3
ddd 30
wok 50
kkk 60
woo 60
whooo 100
1
doo
1
woo
2
easy 1
normal 15
doo 40
woo 60
cant 100
solved 100

3
2
4

100 1 3
1
i
1
joined
1
asakatsu