모티가 식료품을 사다

릭과 모티가 가게에 왔다. 짐작했겠지만 릭은 모티에게 여러 가지 과제를 내주는 것을 좋아하고, 이번에도 예외가 아니다. 모티는 상품 $k$개를 사는 방법의 수를 세야 한다. 가게에는 상품이 총 $n$개 있고, $i$번째 상품의 가격은 $c_i$이다. 릭은 두 수 $l$과 $r$을 모티에게 총 $q$번 준다. 모티는 매번 구입한 상품의 총 가격이 $l$ 이상 $r$ 이하가 되도록 상품 $k$개를 고르는 방법이 몇 가지인지 답해야 한다.

구매는 인덱스 집합 $\{i_1, i_2, \dots, i_k\}$로 나타낸다. 여기서 $i_j$는 $j$번째로 산 상품의 번호이다. 두 구매 $A$와 $B$는 $A_d \neq B_d$인 인덱스 $d$가 있으면 서로 다른 구매로 본다. 따라서 $(1, 2)$와 $(2, 1)$은 서로 다른 두 구매이다. 같은 상품을 여러 번 살 수도 있다.

첫 줄에 세 정수 $n$, $k$, $q$가 주어진다 ($1 \leq n, q \leq 10^5$, $1 \leq k \leq 10^5$). 둘째 줄에는 상품 가격 $c_i$가 $n$개 주어진다 ($1 \leq c_i \leq 5 \cdot 10^4$). 이어지는 $q$개의 줄에는 각각 정수 $l$과 $r$이 주어진다 ($1 \leq l \leq r \leq 5 \cdot 10^4$).

릭이 낸 $q$개의 질문에 대한 답을 한 줄에 하나씩 출력한다. 답이 매우 클 수 있으므로 $786433$으로 나눈 나머지를 출력한다.