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 ~i~ in the cafeteria has ~m_i~ dollars to spend and can extort kindly ask at most one other person, ~v_i~ (~v_i < i~) 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 ~X~ is extorting person ~Y~ for ~a~ dollars and person ~Y~ has ~b~ dollars such that ~b < a~, then person ~Y~ will extort their own victim for ~a-b~ 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 ~N~ 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 ~Q~ 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:

~1 \le N,Q \le 10^5~

~0 \le v_i < i \le N~ (i.e. the index of a victim will be strictly less than the index of the extorter; a victim-index of ~0~ means they have no one to bully.)

~1 \le m_i \le 10^8~

~1 \le p,c \le 10^{14}~

Each person can only extort at most ~1~ person.

Subtask 1 [10%]

~1 \le N,Q \le 100~

Subtask 2 [20%]

~1 \le N \le 1\,000~

Subtask 3 [70%]

No additional constraints.

Input Specification

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

The next line will contain ~N~ space-separated integers, ~m_1 \dots m_N~, representing the amount of money person ~i~ has.

The third line will have ~N~ space-separated integers, ~v_1 \dots v_N~, representing the victim of person ~i~. If ~v_i~ is 0, that means that they can't bully anyone.

Finally, the last ~Q~ lines will contain ~2~ integers each in the form p c, which means that Veshy already possesses ~p~ dollars to spend, but lunch will cost ~c~ dollars.

Output Specification

For each query ~i~, print out the closest person which Veshy can extort such that he will end up with at least as much money as ~c_i~. 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 ~3~ for their money. Since Veshy already possesses a 1 dollar and person ~3~ provides 4 dollars, Veshy will be able to buy lunch, which costs ~5~ dollars. Although there are other ways Veshy could gather 4 dollars, all of the other choices have higher indices than person ~3~. In the third query, Veshy can ask person ~5~ for their money. Since ~1+5<12~, the last person will ask person ~3~ for their money as well. It turns out person ~3~ also doesn't have enough, so this asking-chain continues through persons ~3~ and ~1~, when a cumulative sum of ~5+1+3+1+2=12~ 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.