print2070. Саруман

printСаруман

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Как известно, Саруман Радужный очень любит порядок. Поэтому все полки его войска стоят друг за другом, причем каждый следующий полк содержит количество орков не меньше, чем предыдущий.
Перед тем как напасть на Хельмову Падь, Саруман решил провести несколько вылазок для разведки. Чтобы его отряды никто не заметил, он решил каждый раз отправлять несколько подряд идущих полков так, чтобы суммарное количество орков в них было равно определенному числу. Так как это всего лишь разведка, каждый полк после вылазки возвращается на свое место. Задачу выбрать нужные полки он поручил Гриме Змеиному Языку. А Грима не поскупится на вознаграждение, если вы ему поможете.
В первой строке входного файла находится два целых числа: `n` (`1\ ≤\ n\ ≤\ 2*10^5`) – количество полков и `m` (`1\ ≤\ m\ ≤\ 2*10^5`) – количество предстоящих вылазок. В следующей строке записано `n` чисел `a_i`, где `a_i` – число орков в `i`-ом полке (`1\ ≤\ a_i\ ≤\ 10^9,\ a_i\ ≤\ a_{i+1}`). Далее в `m` строках записаны запросы вида: количество полков `l` (`1\ ≤\ l\ ≤\ n`), которые должны будут отправиться в эту вылазку, и суммарное количество орков в этих полках `s` (`1\ ≤\ s\ ≤\ 2*10^{16}`)
Для каждого запроса выведите номер полка, с которого начнутся те `l`, которые необходимо отправить на вылазку. Если таких полков несколько, выведите любой. Если же так выбрать полки нельзя, выведите `-1`.

Пример ввода

5 2
1 3 5 7 9
2 4
1 3

Пример вывода

1
2
Источник: neerc.ifmo.ru/school
loading