Barry is the coach of a basketball club. There are players in the team, and player has a height of cm.
- Function is the measure of the teamwork between player and . Then .
- Function is the power of set , consisting some players. Then , for all and , where and are players in set .
For example, there are 2 players in set, with , and indexes respectively. Then power of this set is equal to .
The team is going to take part in a tournament. There are rounds in the tournament, each of them having some conditions.
For round , the requirments:
There are three positive integers . To participate in round , Barry needs to find minimal such that there's at least one consecutive subsequence of players between and , where height of each player in this subsequence is at most , and of this subsequence is not less than . If there exists such , Barry's team is able to participate in round . Otherwise, the team is not eligible.
You need to help him determine for every round, is it possible to participate in that round. If it is possible, print minimal for round , otherwise print .
Input Format
The first line contains two integers and - the number of players and rounds respectively.
The second line contains array of postive integers .
The next lines contains three positve integers: .
Constraints
At least for of the total score, .
At least for of the total score, .
Output Format
For every round print minimal if it's possible, otherwise print .
Sample Input 0
5 2
1 1 2 3 4
1 5 2
1 5 11
Sample Output 0
1
2
Sample Input 1
5 4
1 3 2 4 6
1 3 3
1 3 2
2 4 10
1 1 900
Sample Output 1
2
1
3
-1