28866번 - Морти покупает продукты 다국어

문제

Рик и Морти пришли в магазин. Как вы уже поняли, Рик очень любит давать Морти разные задания. И этот случай не является исключением! Сейчас ему нужно подсчитать количество способов купить $k$ продуктов. Всего в магазине $n$ продуктов. Стоимость $i$-го продукта равняется $c_i$. Рик будет $q$ раз давать Морти два числа --- $l$ и $r,ドル Морти в свою очередь должен сказать, сколько существует способов купить $k$ продуктов, чтобы их суммарная стоимость была не меньше $l$ и не больше $r$. Обозначим покупку, как набор индексов ${i_1, i_2, \dots, i_k},ドル где $i_j$ --- номер товара, который был куплен $j$-м. Два способа покупки $A$ и $B$ называются различными, если (индекс товара, купленным $d$-м будем обозначать как $A_d$) существует такой индекс $d,ドル что $A_d \neq B_d$. Таким образом $(1, 2)$ и $(2, 1)$ это два разных способа покупки товаров. Так же, заметьте, что один продукт можно покупать сколько угодно раз.

입력

В первой строке входного файла содержатся три числа $n,ドル $k,ドル $q,ドル $(1 \leq n, q \leq 10^5),ドル $(1 \leq k \leq 10^5)$. Во второй строке находится $n$ целых чисел $c_i$ обозначающих стоимости товаров. Товар с индексом $i$ имеет стоимость $c_i$. $(1 \leq c_i \leq 5 \cdot 10^4)$. Следующие $q$ строк содержат два числа $l$ и $r$ обозначающие вопрос от Рика, $(1 \leq l \leq r \leq 5 \cdot 10^4)$. Морти должен сказать, сколько существует способов купить $k$ продуктов, чтобы их суммарная стоимость была не меньше $l$ и не больше $r$.

출력

В $q$ строках выведите ответы на запросы Рика. Так как ответ может быть очень большим, выведите его по модулю 786433ドル$.

제한

힌트