C. Инна и коробки с конфетами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Инна очень любит сладкое. Перед ней в ряд лежат n закрытых подарочных коробочек. В каждой из этих коробочек либо лежит конфета (Дима постарался), либо ничего не лежит (Сережа постарался). Будем считать, что коробочки пронумерованы от 1 до n слева направо.

Так как коробочки закрыты, Инна не знает, в каких коробочках лежат конфеты, а в каких — нет. Для того, чтобы узнать это, Инна выбрала число k и задала w вопросов Диме. Каждый вопрос характеризуется двумя целыми числами li, ri (1 ≤ li ≤ ri ≤ n; r - l + 1 делится на k), i-ый вопрос: «Дима, правда, что среди коробочек с номерами от li до ri включительно конфеты лежат исключительно в коробочках с номерами li + k - 1, li + 2k - 1, li + 3k - 1, ..., ri?»

Дима очень не любит говорить Инне: «Нет!». Поэтому ему интересно, какое количество действий придется совершить для каждого вопроса, чтобы ответ на вопрос был положительным. За одно действие Дима может либо незаметно достать конфету из любой коробки, либо незаметно положить конфету в любую коробку (у Димы бесконечно много конфет). Помогите Диме, посчитать количество действий для каждого вопроса Инны.

Обратите внимание, что Дима не меняет массив во время вопросов Инны. Поэтому когда ведется подсчет количества операций для текущего вопроса, считается, что последовательность коробочек не изменялась.

Входные данные

Первая строка входных данных содержит три целых числа n, k и w (1 ≤ k ≤ min(n, 10), 1 ≤ n, w ≤ 105). Вторая строка содержит n символов. Если в i-ой коробочке лежит конфета, i-ый символ строки равен 1, иначе — 0.

Каждая из следующих w строк содержат по два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — описание i-го вопроса. Гарантируется, что ri - li + 1 делится на k.

Выходные данные

Для каждого вопроса в отдельной строке выведите целое число — минимальное количество операций необходимых Диме, чтобы ответ на вопрос стал положительным.

Примеры
Входные данные
10 3 3
1010100011
1 3
1 6
4 9
Выходные данные
1
3
2
Примечание

Чтобы удовлетворить первый вопрос придется забрать из первой коробки конфету. Поэтому ответ — 1.

Для второго вопроса нужно забрать из первой коробки конфету, забрать из пятой коробки конфету и положить в шестую коробку конфету. Ответ — 3.

Для третьего вопроса нужно забрать конфету из второй коробки и положить в третью. Ответ — 2.