 | Работники 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}\).
Выходные данные
Для каждого из \(q\) запросов выведите ответ на задачу.
Примечание
Рассмотрим первый пример.
В первую минуту \(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'.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1
|
3
4
5
6
7
|