Задачі
Бочки Гомера Симпсона
Бочки Гомера Симпсона
У Гомера Симпсона имеются бочки - разные виды бочек чтобы содержать разные виды жидкостей. Например, бочки для воды, бочки для нефти и так далее. Он держит эти бочки в подвале (т.е., ниже первого этажа) своего дома в последовательном порядке. Каждая бочка имеет емкость, равную объему соответствующей жидкости, которой она максимально заполнена.
Обозначим емкость \textbf{i}-ой бочки через \textbf{Cap}\[\textbf{i}\]. Переномеруем все \textbf{n} бочек, начиная с \textbf{1}. То есть \textbf{1}-ая бочка имеет емкость \textbf{Cap}\[\textbf{1}\], ..., \textbf{n}-ая бочка имеет емкость \textbf{Cap}\[\textbf{n}\]. В настоящее время сын Гомера Барт занимается кражей жидкостей из городского супермаркета. Он крадет воду, масло, йогурт, и т.д. - все что является жидкостью. Каждый день Барт приходит к своему отцу со специфической жидкостью \textbf{l} с объемом \textbf{v}. Гомер не против таких событий, так как все что бесплатно - приемлемо по законам семьи Симпсонов. Гомер выливает жидкость в одну из соответствующих бочек, следуя стратегии, которую назвал "Симпсон Бочку Найди Алгоритм" (\textbf{СБНА}):
Сначала он находит все бочки, имеющие свободный объем ≥ \textbf{v} (изначально свободный объем каждой бочки равен ее емкости). Если существует несколько вариантов, то он находит все бочки, свободный объем которых наименьший. Если и таких бочек несколько, то Гомер выбирает бочку с наименьшим индексом.
Пусть Гомер выбрал бочку с индексом \textbf{b}, следуя \textbf{СБНА}. Тогда Гомер и Барт выливают жидкость в \textbf{b}-ую бочку, вследствие чего свободный объем \textbf{b}-ой бочки уменьшается на \textbf{v}.
\InputFile
Первая строка содержит \textbf{3} числа: \textbf{n (1} ≤ \textbf{n }≤\textbf{ 1000000) }- количество бочек в подвале, \textbf{L} (\textbf{1} ≤ \textbf{L }≤ \textbf{1000}) - количество типов жидкости, \textbf{q }- количество различных дней, в которые Барт что-нибудь крал из супермаркетов(число запросов, \textbf{1 }≤ \textbf{q }≤ \textbf{100000}).
Следующая строка содержит \textbf{n} целых чисел, \textbf{i}-ое число равно \textbf{Cap}\[\textbf{i}\] - емкости \textbf{i}-ой бочки (изначально объем свободный, \textbf{1} ≤ \textbf{Cap}\[\textbf{i}\] ≤ \textbf{10^9}). Следующая строка содержит \textbf{n} целых числе, \textbf{i}-ое число равно некоторому значению \textbf{l}, которое указывает на тип \textbf{i}-ой бочки (масло, вода, мыло, йогурт, и т.д., \textbf{1} ≤ \textbf{l} ≤ \textbf{L}).
Следующие \textbf{q} строк содержат запросы. \textbf{i}-ый запрос задается двумя числами \textbf{l} и \textbf{v}, разделенными пробелом (\textbf{1} ≤ \textbf{l} ≤ \textbf{L}, \textbf{1} ≤ \textbf{v} ≤ \textbf{10^9}).
\OutputFile
Для каждого запроса выведите в отдельной строке индекс бочки \textbf{b} (\textbf{1} ≤ \textbf{b} ≤ \textbf{n}), которую найдет \textbf{СБНА} в результате обработки запроса.
Отметим, что если по окончанию \textbf{СБНА} соответствующей бочки со свободным объемом не найдется, то Гомер и Барт могут игнорировать жидкость. В этом случае следует вывести \textbf{-1}.
Вхідні дані #1
3 2 9 400 100 600 1 2 1 1 500 1 200 1 50 2 50 1 300 1 199 1 51 2 51 2 50
Вихідні дані #1
3 1 3 2 -1 1 -1 -1 2