$1$부터 $n$까지의 정수로 이루어진 순열을 고려하자. 이제 $1$부터 $n$까지의 각 숫자를 문맥 자유 문법(Context-Free Grammar, CFG)의 비단말 기호(non-terminal)라고 생각하자. 각 숫자 $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$ $\downarrow$ $1\ 4\ 3\ 2$

두 번째 단계는 다음과 같다:

$1\ 4\ 3\ 2$ $\downarrow$ $1\ 1\ 4\ 3\ 2\ 1\ 3\ 2\ 1\ 2$

세 번째 단계는 다음과 같다:

$1\ 1\ 4\ 3\ 2\ 1\ 3\ 2\ 1\ 2$ $\downarrow$ $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$는 최종 리스트의 길이를 초과하지 않음)가 주어진다. 이는 과정에 의해 생성된 리스트의 처음 $a$개 요소 중에서 정수 $k$가 나타나는 횟수에 대한 질의이다.

출력

각 질의에 대해, 입력에 나타난 순서대로 질의에 대한 답인 정수를 한 줄에 하나씩 출력한다.

예제

입력 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