問題文

りんたろう君はバーチャルコンテスト「あさかつ」によく参加しています。

あさかつでは AtCoder の過去問（以下、単に問題と表現します）から相異なる $6$ 問が毎回ランダムに出題されます。
問題はその問題名で区別され、問題 $P$ と問題 $P'$ は $P = P'$ である時、かつその時に限り、同じ問題です。
問題名は英小文字からなる文字列として与えられます。

りんたろう君はあさかつの問題を $1$ 番目の問題から順に、$60$ 分で可能な限り解きます。

• より厳密には、$i \ (1 \leq i \leq 6)$ 番目の問題を解くのにかかる時間が $x_i$ 分である場合、
  $x_1 + x_2 + \cdots + x_k \leq 60$ を満たす最大の正整数 $k$ $(1 \leq k \leq 6)$ を取り、$k$ 番目の問題まで解きます。
  そのような $k$ が存在しない場合は $1$ 問も解きません。

ここで、りんたろう君は今まで解いた問題のうち、直近 $N$ 問の問題に「既視感」を持っています。
解くのにかかる時間が $d$ 分の問題 $P$ に既視感を持っている時、かつその時に限り、問題 $P$ を $\min(d, K)$ 分で解きます。
なお、「直近 $N$ 問の問題」の厳密な説明は後述します。

クエリが $Q$ 個与えられます。クエリは以下の $2$ 種類のいずれかです。

• クエリ $1$: 問題 $s$ を解く。
• クエリ $2$: あさかつに参加する。$i \ (1 \leq i \leq 6)$ 番目の問題は問題 $t_i$ であり、解くのにかかる時間は $d_i$ 分である。

$Q$ 個のクエリを以下の通りに処理してください。
また、クエリ $2$ が与えられる度に、りんたろう君がそのあさかつで解いた問題の個数を $1$ 行に出力してください。

• $A$ を「今まで解いた問題を並べた配列」と定義して、その要素数を $M$ とします。はじめ $A$ は空です。
• $i = 1, 2, \dots, Q$ の順に $i$ 番目のクエリを以下の手順で処理します。
• クエリ $1$ の場合
• $A$ の末尾に問題 $s$ を追加します。
• クエリ $2$ の場合
• $j = \max(1,M-N+1)$ とおき、$B = (A_j, A_{j+1}, \dots, A_M)$ としたとき（$M = 0$ の場合、$B$ は空）、
  ある問題 $P$ が $B$ に含まれる時、かつその時に限り、りんたろう君は問題 $P$ に既視感を持っています。
• そのクエリで与えられるあさかつの問題を $1$ 番目の問題から順に解きます。
• あさかつ終了後に、そのあさかつで解いた問題全てを、解いた順に $A$ の末尾に追加します。

既視感の条件について、例えば $A = ($a, s, a, ka, tsu$)$ の場合は以下のようになります。

• $N = 1$ の場合、$B = ($tsu$)$ です。
• $N = 2$ の場合、$B = ($ka, tsu$)$ です。
• $N = 3$ の場合、$B = ($a, ka, tsu$)$ です。
• $N = 4$ の場合、$B = ($s, a, ka, tsu$)$ です。
• $N = 5$ の場合、$B = ($a, s, a, ka, tsu$)$ です（$N = 6, 7, \dots$ も同様）。

入力

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

• $i$ 番目のクエリ $\mathrm{Query}_i \ (1 \leq i \leq Q)$ は以下のいずれかの形式で与えられる。
• $i$ 番目のクエリがクエリ $1$ のとき:

  $1$
  $s$
  

• $i$ 番目のクエリがクエリ $2$ のとき:

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

• 文字列以外の入力はすべて整数
• $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$ は英小文字からなる文字列
• $1 \leq |s|, |t_i| \leq 10 \ (1 \leq i \leq 6)$
• 各クエリ $2$ の $t_1, t_2, \dots, t_6$ は相異なる

出力

クエリ $2$ が与えられる度に、りんたろう君がそのあさかつで解いた問題の個数を $1$ 行に出力してください。

サンプル

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