Бочки Гомера Симпсона
У Гомера Симпсона имеются бочки - разные виды бочек чтобы содержать разные виды жидкостей. Например, бочки для воды, бочки для нефти и так далее. Он держит эти бочки в подвале (т.е., ниже первого этажа) своего дома в последовательном порядке. Каждая бочка имеет емкость, равную объему соответствующей жидкости, которой она максимально заполнена.
Обозначим емкость i-ой бочки через Cap[i]. Переномеруем все n бочек, начиная с 1. То есть 1-ая бочка имеет емкость Cap[1], ..., n-ая бочка имеет емкость Cap[n]. В настоящее время сын Гомера Барт занимается кражей жидкостей из городского супермаркета. Он крадет воду, масло, йогурт, и т.д. - все что является жидкостью. Каждый день Барт приходит к своему отцу со специфической жидкостью l с объемом v. Гомер не против таких событий, так как все что бесплатно - приемлемо по законам семьи Симпсонов. Гомер выливает жидкость в одну из соответствующих бочек, следуя стратегии, которую назвал "Симпсон Бочку Найди Алгоритм" (СБНА):
Сначала он находит все бочки, имеющие свободный объем ≥ v (изначально свободный объем каждой бочки равен ее емкости). Если существует несколько вариантов, то он находит все бочки, свободный объем которых наименьший. Если и таких бочек несколько, то Гомер выбирает бочку с наименьшим индексом.
Пусть Гомер выбрал бочку с индексом b, следуя СБНА. Тогда Гомер и Барт выливают жидкость в b-ую бочку, вследствие чего свободный объем b-ой бочки уменьшается на v.
Входные данные
Первая строка содержит 3 числа: n (1 ≤ n ≤ 1000000) - количество бочек в подвале, L (1 ≤ L ≤ 1000) - количество типов жидкости, q - количество различных дней, в которые Барт что-нибудь крал из супермаркетов(число запросов, 1 ≤ q ≤ 100000).
Следующая строка содержит n целых чисел, i-ое число равно Cap[i] - емкости i-ой бочки (изначально объем свободный, 1 ≤ Cap[i] ≤ 10^9). Следующая строка содержит n целых числе, i-ое число равно некоторому значению l, которое указывает на тип i-ой бочки (масло, вода, мыло, йогурт, и т.д., 1 ≤ l ≤ L).
Следующие q строк содержат запросы. i-ый запрос задается двумя числами l и v, разделенными пробелом (1 ≤ l ≤ L, 1 ≤ v ≤ 10^9).
Выходные данные
Для каждого запроса выведите в отдельной строке индекс бочки b (1 ≤ b ≤ n), которую найдет СБНА в результате обработки запроса.
Отметим, что если по окончанию СБНА соответствующей бочки со свободным объемом не найдется, то Гомер и Барт могут игнорировать жидкость. В этом случае следует вывести -1.