問題文

文字列 \(X\) と文字列集合 \(X'\) があります。

初期状態では \(X=S\)であり、\(X'\) には文字列 \(S\) のみが1個入っている状態です。

ここに、次の操作を \(N\) 回します。

・ \(i\) 回目の操作では \(X\) の語尾から \(a_i\) 文字を削除し、 \(X\) の語尾に文字列 \(b_i\) を連結させ、 \(X\) を \(X'\) に追加する

なお、どの操作でもその操作を始めるタイミングでは \(X\) が \(a_i\) 文字以上であることが保証されます。

このとき、 \(N\) 回の操作を終えると、 \(X'\) には \(N+1\) 個の文字列が入っている状態になります。

\(N\) 回の操作の後に次の形のクエリが \(Q\) 個与えられるので、それを順番に処理して下さい。

・ \(i\) 個目のクエリでは、 \(X'\) の中に入っている文字列の中で文字列 \(T_i\) がprefixであるものの個数を答える。

入力

\(N\) \(S\)

\(a_1\) \(b_1\)

\(a_2\) \(b_2\)

:

\(Q\)

\(T_1\)

\(T_2\)

:

\(T_Q\)

出力

\(Q\)行出力しなさい。\(i\)行目には\(i\)個目のクエリに対する答えを出力しなさい。

制約

• \(1≦N,Q≦3\times10^5\)


• \(0≦a_i≦3\times10^5\)


• \(1≦(|b_i|\) の和\()≦3\times10^5\)


• \(1≦|S|≦3\times10^5\)


• \(1≦(|T_i|\) の和\()≦3\times10^5\)

小課題

小課題 Short

• \(1≦N,Q≦4\times10^3\)


• \(1≦a_i,|b_i|,|T_i|,|S|≦4\times10^3\)


• \(X\) は常に \(4\times10^3\) 文字を超えない

小課題 Long

• \(1≦N,Q≦4\times10^3\)


• \(1≦a_i,|b_i|,|T_i|≦4\times10^3\)


• \(X\) は常に \(296\) \(000\) 文字を下回らない

小課題 Non-Decreasing

• \(a_i=0\)

小課題 Euglena

• 追加の制約はない。