考慮一個 $1$ 到 $n$ 的整數排列。現在，將每個數字 $1$ 到 $n$ 視為上下文無關文法（Context-Free Grammar, 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$ 開始的過程，在每一步中，應用這些規則來建立一個新的整數列表。在上述例子中，第一步：

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

第二步：

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

第三步：

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

給定一個排列、步驟數以及一系列詢問，詢問在該過程所建立列表的前綴中，特定整數出現的次數，請回答所有的詢問。

輸入格式

第一行包含三個整數 $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$ 行，每行包含兩個整數 $k$ ($1 \le k \le n$) 和 $a$ ($1 \le a \le 10^9$，$a$ 不會超過最終列表的長度)。這是一個關於整數 $k$ 在該過程所建立列表的前 $a$ 個元素中出現次數的詢問。

輸出格式

輸出 $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