Морти покупает продукты

Рик и Морти пришли в магазин. Как вы уже поняли, Рик очень любит давать Морти разные задания. И этот случай не является исключением! Сейчас ему нужно подсчитать количество способов купить $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$.