SOLVE
LATER
Queen Vasya is preparing for a war against Rhezo. She has N warriors in total arranged in a line. Let us number the warriors by numbers from 1 to N. She will fight Rhezo's army for Q days, and each day she can choose only one warrior.
For each warrior, we know 2 values associated with him, let us call these A and B. Each day Vasya can choose her warrior from a range \(L_i\) to \(R_i\), she must choose the warrior with maximum A value. If there is more than 1 warrior having the same maximum A value, she chooses the warrior with minimum B value. If still there is more than 1 warrior with same maximum A value and same minimum B value, she chooses the one with lower index in line.
You being the hand of Queen Vasya, need to help her in choosing the warrior for each day.
Input:
First line contains a single integer N, denoting the number of warriors Queen Vasya has. Second line contains N space separated integers \(A_i\). Third line contains N space separated integers \(B_i\). Next line contains a single integer Q, denoting the number of days Queen Vasya chooses a warrior. Each of the next Q lines contains 2 integers \(L_i\) and \(R_i\).
Output:
For each \(L_i\) and \(R_i\), print the index of the warrior that Queen Vasya should choose.
Constraints:
\(1 \le N, Q \le 10^6\)
\(1 \le A_i, B_i \le 10^9\)
\(1 \le L_i \le R_i \le N\)
For the last query, both warrior number 2 and warrior number 5 have the same maximum A value, but we will choose warrior 5 because he has a lower B value.