$1$ から $n$ までの整数の順列を考えます。ここで、$1$ から $n$ までの各数を文脈自由文法（CFG）における非終端記号とみなします。各数 $k$ は、順列の順序に従って $1$ から $k$ までの整数のリストに展開されます。例えば、$n = 4$ で順列が $1, 4, 3, 2$ の場合、以下のようになります。

$1 \implies 1$ $2 \implies 1, 2$ $3 \implies 1, 3, 2$ $4 \implies 1, 4, 3, 2$

次に、$n$ から開始し、各ステップでこれらの規則を適用して新しい整数のリストを作成するプロセスを考えます。上記の例では、第1ステップは以下の通りです。

$$4 \implies 1, 4, 3, 2$$

第2ステップは以下の通りです。

$$1, 4, 3, 2 \implies 1, (1, 4, 3, 2), (1, 3, 2), (1, 2)$$

第3ステップは以下の通りです。

$$1, 1, 4, 3, 2, 1, 3, 2, 1, 2 \implies 1, 1, (1, 4, 3, 2), (1, 3, 2), (1, 2), 1, (1, 3, 2), (1, 2), 1, (1, 2)$$

順列、ステップ数、およびプロセスによって作成されたリストの接頭辞における特定の整数の出現回数を問うクエリのリストが与えられたとき、すべてのクエリに答えてください。

入力

入力の最初の行には、3つの整数 $n$ ($2 \le n \le 10^5$)、$s$ ($1 \le s \le 5$)、$q$ ($1 \le q \le 2 \cdot 10^5$) が含まれます。ここで、$n$ は順列のサイズ、$s$ はプロセスを適用するステップ数、$q$ はクエリの数です。

続く $n$ 行の各行には、単一の整数 $p$ ($1 \le p \le n$) が含まれます。これは順列を順に表したものです。$p$ の値はすべて異なります。

続く $q$ 行の各行には、2つの整数 $k$ ($1 \le k \le n$) と $a$ ($1 \le a \le 10^9$、$a$ は最終的なリストの長さを超えない) が含まれます。これは、プロセスによって作成されたリストの最初の $a$ 個の要素における整数 $k$ の出現回数を問うクエリです。

出力

$q$ 行を出力してください。各行には、入力された順序でクエリに対する答えとなる単一の整数を出力してください。

入出力例

入力 1

4 3 6
1
4
3
2
1 6
2 20
4 1
3 5
2 9
1 16

出力 1

3
6
0
1
2
8