순열 CFG

정수 $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$에서 시작해 각 단계마다 이 규칙을 적용해 정수의 새 리스트를 만드는 과정을 생각하자. 위 예에서 첫 단계에서는:

$\overbrace{1 \; 4 \; 3 \; 2}^{4}$

둘째 단계에서는:

$\overbrace{1}^{1} \overbrace{1 \; 4 \; 3 \; 2}^{4} \; \overbrace{1 \; 3 \; 2}^{3} \; \overbrace{1 \; 2}^{2}$

셋째 단계에서는:

$\overbrace{1}^{1} \overbrace{1}^{1} \overbrace{1 \; 4 \; 3 \; 2}^{4} \; \overbrace{1 \; 3 \; 2}^{3} \; \overbrace{1 \; 2}^{2} \overbrace{1}^{1} \overbrace{1 \; 3 \; 2}^{3} \; \overbrace{1 \; 2}^{2} \overbrace{1}^{1} \overbrace{1 \; 2}^{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$가 몇 번 나타나는지 묻는 쿼리다.

쿼리의 답을 입력에 주어진 순서대로 $q$개 줄에 하나씩 출력한다.