Xét một hoán vị của các số nguyên từ $1$ đến $n$. Bây giờ, hãy coi mỗi số từ $1$ đến $n$ là một ký hiệu không kết thúc trong một Văn phạm phi ngữ cảnh (CFG). Mỗi số $k$ mở rộng thành một danh sách các số nguyên từ $1$ đến $k$ theo thứ tự của hoán vị. Ví dụ, nếu $n = 4$ và hoán vị là $1\ 4\ 3\ 2$:

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

Bây giờ, hãy xem xét một quá trình bắt đầu với $n$, và tại mỗi bước, áp dụng các quy tắc này để tạo ra một danh sách các số nguyên mới. Trong ví dụ trên, tại bước đầu tiên:

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

Tại bước thứ hai:

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

Tại bước thứ ba:

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

Cho một hoán vị, một số bước, và một danh sách các truy vấn hỏi về số lần xuất hiện của một số nguyên cụ thể trong một tiền tố của danh sách được tạo ra bởi quá trình này, hãy trả lời tất cả các truy vấn.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n$ ($2 \le n \le 10^5$), $s$ ($1 \le s \le 5$) và $q$ ($1 \le q \le 2 \cdot 10^5$), trong đó $n$ là kích thước của hoán vị, $s$ là số bước áp dụng quá trình, và $q$ là số lượng truy vấn.

Mỗi dòng trong số $n$ dòng tiếp theo chứa một số nguyên $p$ ($1 \le p \le n$). Đây là hoán vị theo thứ tự. Tất cả các giá trị của $p$ sẽ khác nhau.

Mỗi dòng trong số $q$ dòng tiếp theo chứa hai số nguyên $k$ ($1 \le k \le n$) và $a$ ($1 \le a \le 10^9$, $a$ sẽ không vượt quá độ dài của danh sách cuối cùng). Đây là một truy vấn về số lần xuất hiện của số nguyên $k$ trong $a$ phần tử đầu tiên của danh sách được tạo ra bởi quá trình.

Dữ liệu ra

Xuất ra $q$ dòng, mỗi dòng là một số nguyên duy nhất, là câu trả lời cho các truy vấn theo thứ tự xuất hiện trong dữ liệu vào.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
6
0
1
2
8