Бочки Гомера Сімпсона
У Гомера Сімпсона є різні бочки для зберігання різних видів рідин, таких як вода, нафта тощо. Він зберігає ці бочки в підвалі свого будинку в певному порядку. Кожна бочка має певну ємність, яка відповідає максимальному об'єму рідини, що може в ній зберігатися.
Позначимо ємність i-ої бочки як Cap[i]. Всі n бочок пронумеровані від 1 до n. Тобто, 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-е число вказує на тип i-ої бочки (олія, вода, мило, йогурт тощо, 1 ≤ l ≤ L).
Наступні q рядків містять запити. i-ий запит задається двома числами l і v, розділеними пробілом (1 ≤ l ≤ L, 1 ≤ v ≤ 10^9).
Вихідні дані
Для кожного запиту виведіть в окремому рядку індекс бочки b (1 ≤ b ≤ n), яку знайде СБЗА в результаті обробки запиту.
Якщо після виконання СБЗА відповідної бочки з вільним об'ємом не знайдеться, Гомер і Барт можуть ігнорувати рідину. У цьому випадку слід вивести -1.