G. Эла на уроке танцев
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Работники DTL любят вечеринки по выходным. Эла тоже! К сожалению, она еще не умеет танцевать. Поэтому она решила пойти на урок танцев.

В танцевальном классе $$$n$$$ студентов, включая Элу. В финальном проекте $$$n$$$ студентов примут участие в композиции, описанной ниже.

$$$n$$$ студентов расположатся на положительной стороне оси $$$Ox$$$. $$$i$$$-й танцор будет находиться в точке $$$a_i > 0$$$. Некоторые танцоры будут менять положение во время танца (назовем их подвижными танцорами), а другие будут оставаться на одном месте во время композиции (назовем их неподвижными танцорами). Обозначим танцоров с помощью бинарной строки $$$s$$$ длины $$$n$$$: если $$$s_i$$$ равно '1', то $$$i$$$-й танцор подвижный, иначе $$$i$$$-й танцор неподвижный. Хотя бы один танцор является подвижным.

Назовем значением положительной энергии композиции число $$$d > 0$$$. Танцоры будут выполнять движения на основе этого значения.

Каждую минуту после начала танца подвижный танцор с наименьшей координатой $$$x$$$ начинает движение вправо. В начале движения уровень энергии танцора будет равен значению положительной энергии композиции, то есть $$$d$$$. Каждый раз, когда этот танцор перемещается с какой-то координаты $$$y$$$ на координату $$$y+1$$$, уровень его энергии будет уменьшаться на $$$1$$$. В какой-то момент танцор может встретить другого танцора (возможно, это произойдет несколько раз), в той координате, где он окажется. Если это произойдет, то уровень энергии танцора повысится на $$$1$$$. Танцор перестанет двигаться вправо, когда его уровень энергии достигнет $$$0$$$, и при этом он не стоит на одной координате с каким-либо другим танцором.

Танцоры очень хорошо подготовлены, и каждое движение заканчивается до того, как начинается следующая минута.

Чтобы показать свое понимание этой композиции, Эла должна ответить на $$$q$$$ запросов, каждый из которых состоит из двух целых чисел $$$k$$$ и $$$m$$$. Ответом на этот запрос является координата $$$m$$$-го танцора (любого типа) слева на $$$k$$$-й минуте после начала композиции. Другими словами, обозначим как $$$x_{k, 1}, x_{k, 2}, \dots, x_{k, n}$$$ отсортированные координаты танцоров на $$$k$$$-й минуте от начала, вам нужно вывести $$$x_{k, m}$$$.

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

Первая строка содержит три целых числа $$$n$$$, $$$d$$$ и $$$q$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le d \le 10^9$$$; $$$1 \le q \le 10^5$$$ ) — количество танцоров, значение положительной энергии композиции и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < \dots < a_n \le 10^9$$$) — координаты танцоров.

Третья строка содержит бинарную строку $$$s$$$ длины $$$n$$$ — показатель подвижности каждого танцора. Каждый символ равен '0' или '1', где '0' обозначает неподвижность очередного танцора, а '1' подвижного. Гарантируется, что $$$s$$$ содержит хотя бы один символ '1'.

Далее следуют $$$q$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$k_i$$$ и $$$m_i$$$ ($$$1 \le k_i \le 10^9$$$, $$$1 \le m_i \le n$$$) — очередной запрос.

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

Для каждого из $$$q$$$ запросов выведите ответ на задачу.

Примеры
Входные данные
4 3 8
1 3 6 7
1011
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
Выходные данные
3
5
6
7
3
6
7
10
Входные данные
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1
Выходные данные
3
4
5
6
7
Примечание

Рассмотрим первый пример.

В первую минуту $$$1$$$ — это самая маленькая координата среди подвижных танцоров. Энергия танцора изначально равна $$$3$$$. Затем происходит следующее:

  • Танцор перемещается с $$$1$$$ на $$$2$$$. Уровень энергии снизился до $$$2$$$.
  • Танцор перемещается с $$$2$$$ на $$$3$$$. Уровень энергии снизился до $$$1$$$, а затем увеличился до $$$2$$$, когда он встретил другого танцора в координате $$$3$$$.
  • Танцор перемещается с $$$3$$$ на $$$4$$$. Уровень энергии снизился до $$$1$$$.
  • Танцор перемещается с $$$4$$$ на $$$5$$$. Уровень энергии снизился до $$$0$$$.

В конце первой минуты отсортированные координаты танцоров становятся $$$[3, 5, 6, 7]$$$, а их соответствующая подвижность равна '0111'.

На второй минуте $$$5$$$ — самая маленькая координата среди подвижных танцоров. Энергия танцора изначально равна $$$3$$$. Затем происходит следующее:

  • Танцор перемещается с $$$5$$$ на $$$6$$$. Уровень энергии снизился до $$$2$$$, а затем увеличился до $$$3$$$, когда он встретил другого танцора в координате $$$6$$$.
  • Танцор перемещается с $$$6$$$ на $$$7$$$. Уровень энергии снизился до $$$2$$$, а затем увеличился до $$$3$$$, когда он встретил другого танцора в координате $$$7$$$.
  • Танцор перемещается с $$$7$$$ на $$$8$$$. Уровень энергии снизился до $$$2$$$.
  • Танцор перемещается с $$$8$$$ на $$$9$$$. Уровень энергии снизился до $$$1$$$.
  • Танцор перемещается с $$$9$$$ на $$$10$$$. Уровень энергии снизился до $$$0$$$.

В конце второй минуты отсортированные координаты танцоров становятся $$$[3, 6, 7, 10]$$$, а их соответствующая подвижность равна '0111'.