It's lunchtime! Lunchtime at Veshy's school can often prove to be a tricky thing, since the cafeteria loves to change their prices on a regular basis. As such, Veshy sometimes doesn't have enough money to afford lunch!

Luckily, there exists a pecking order in the cafeteria! Each person in the cafeteria has dollars to spend and can ~~extort~~ kindly ask at most one other person, () for their lunch money. If the person being asked doesn't have enough money to cover the costs, then the person being asked can ask their own respective ~~victim~~ friend for money, and so on. (i.e. if person is extorting person for dollars and person has dollars such that , then person will extort their own victim for dollars, which repeats until the whole chain coughs up enough money.)

Since Veshy sits right at the top of the pecking order, he gets the special privilege of being able to extort any **one** of the other people in the cafeteria for their money. However, with great privilege comes great laziness, and as such, Veshy wishes to pick the person sitting **closest** to him who can supply him with enough money to buy lunch.

Veshy isn't quite sure what the cafeteria will set the lunch price to be today, so he's going to ask you queries to figure out who he should ~~extort~~ ask for money. Help Veshy out to avoid being extorted as well!

**Note**: **closest** is defined here as the person with the least index that still satisfies the conditions.

#### Constraints

For all subtasks:

(i.e. the index of a victim will be strictly less than the index of the extorter; a victim-index of means they have no one to bully.)

Each person can only extort at most person.

##### Subtask 1 [10%]

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No additional constraints.

#### Input Specification

The first line will contain , the number of people in the cafeteria today (other than Veshy), and , the number of queries.

The next line will contain space-separated integers, , representing the amount of money person has.

The third line will have space-separated integers, , representing the victim of person . If is `0`

, that means that they can't bully anyone.

Finally, the last lines will contain integers each in the form `p c`

, which means that Veshy already possesses dollars to spend, but lunch will cost dollars.

#### Output Specification

For each query , print out the **closest** person which Veshy can extort such that he will end up with at least as much money as .
Note that Veshy may already possess enough money to pay off the cost outright, which means he doesn't need to extort anyone.
Veshy may also be unable to pay for lunch no matter who he chooses to extort.
In either of these two cases, print out `-1`

.

#### Sample Input 1

```
5 4
2 1 4 3 1
0 1 1 2 3
3 2
1 5
5 12
100 100
```

#### Sample Output 1

```
-1
3
5
-1
```

#### Explanation of Sample Output 1

For the first query and last query, Veshy already has enough money to pay for lunch by himself. In the second query, Veshy should kindly ask person for their money. Since Veshy already possesses a 1 dollar and person provides 4 dollars, Veshy will be able to buy lunch, which costs dollars. Although there are other ways Veshy could gather 4 dollars, all of the other choices have higher indices than person . In the third query, Veshy can ask person for their money. Since , the last person will ask person for their money as well. It turns out person also doesn't have enough, so this asking-chain continues through persons and , when a cumulative sum of dollars have been accumulated, which is just enough.

#### Sample Input 2

```
5 1
999 999 999 999 999
0 1 2 3 4
999 10000000
```

#### Sample Output 2

`-1`

#### Explanation of Sample Output 2

No matter who Veshy chooses to ask, it is never possible to accumulate enough money to buy lunch.

## Comments

What a wonderful little problem! A couple kinds of dynamic programming, binary search -- I think this is a great problem to help teach those topics.

(I do think that the 'data structures' and 'graphs' problem types are inaccurate, though. There are no cycles and I can't see why a graph formulation would be beneficial.)

Thank you!

Is there a better solution than QN time complexity?

The intended time complexity is , and there are methods to achieve as well.