Marisa planted $n$ apple trees in a row, the $i^{th}$ tree product apples of size $A_i$. There are $q$ customers who wish to purchase apples. Each customer, denoted by the index $i$, has a specific requirement of purchasing $a_i$ apples within a given size range, $[l_i, r_i]$. Additionally, each customer starts purchasing apples from tree $x_i$. Whenever a customer encounters an apple tree that offers apples within their desired size range, they will purchase one apple from that tree. Once a customer has bought the required number of apples, they will stop purchasing. Help Marisa determine for each customer, at which tree will he stop.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line four integers $l_i,r_i,x_i,a_i$.
### Output
- Print $q$ integers, the $i^{th}$ integer is the tree at which customer $i$ will stop. In case the customer cannot buy enough apples, print `-1`.
### Constraints
- $1 \le n,q \le 10^5$.
- $1 \le A_i \le 10^5$.
- $1 \le l_i \le r_i \le 10^5$.
- $1 \le x_i,a_i \le n$.
### Example
Input:
```
9 10
10 6 6 10 6 6 7 9 3
10 14 9 1
9 12 3 1
5 18 5 2
13 17 9 2
2 7 3 2
6 14 2 2
5 12 4 2
3 11 3 1
7 11 5 1
15 19 5 2
```
Output:
```
-1 4 6 -1 5 3 5 3 7 -1
```
