Homer Simpsons barrels
Homer Simpson has barrels - there are different kinds of barrels to hold different kinds of liquids. For example, water barrels, oil barrels and so on. He keeps these barrels on a basement (i.e, below the ground floor) of his house in sequential order. Each barrel has capacity, which is equal to the volume of the liquid, when this barrel is filled as much as possible, with corresponding liquid.
Let's denote the capacity of i's barrel with Cap[i]. There are n barrels and numbering of them begins with 1. So that, 1st barrel has Cap[1] capacity, ..., nth barrel has Cap[n] capacity. Nowadays, Homer's son Bart Simpson is involved to stole liquids from city markets. He steals water, oil, yogurt, etc. - everything that can be specified as liquid. Everyday Bart comes to his father with specific liquid l, having volume v. Homer is not opposite to this situation, because everything, which is free, is acceptable by the laws of Simpson family. Homer tries to pour the liquid to one of the corresponding barrels. He does this using following strategy, which is called "Simpson Barrel Finding Algorithm" (SBFA):
First, he finds all barrels which have their free volume ≥ v (initially, the free volume of each barrel is equal to its capacity). If there are several choices, he then finds all barrels which have their free volume as least as possible. If there are again several choices, Homer chooses barrel with minimum index.
Let's say that, he chose the barrel with index b, using SBFA. Then Homer and Bart pour the liquid to b'th barrel, so free volume of b'th barrel decreases by v, from now on.
Input
First line contains 3 integers: n - number of barrels on basement (1 ≤ n ≤ 1000000), L - number of liquid types 1 ≤ L ≤ 1000), q - number of distinct days, on which Bart stole something from markets (number of queries, 1 ≤ q ≤ 100000).
Following line contains n integers, i'th integer equals to Cap[i]-capacity of i'th barrel (initial free volume, 1 ≤ Cap[i] ≤ 10^9). Next line contains n integers, i'th integer equals to some number l - which indicates the type of i'th barrel (oil, water, soap, yogurt, etc., 1 ≤ l ≤ L).
Next q lines contain queries. i'th query is defined by 2 numbers l and v, separated by space (1 ≤ l ≤ L, 1 ≤ v ≤ 10^9). Output
For each query you need to output on a separate line the index of the barrel b (1 ≤ b ≤ n), which SBFA finds after processing this query.
Notice that, after SBFA finishes, Homer and Bart may ignore the liquid, if there is no corresponding barrel with enough free volume. In this case, output -1.