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
```