Despite your best efforts, Mr. Purple has discovered that cheating has occurred in your class. There are students, numbered from to , and each student has chosen someone to scapegoat — the -th student will blame student .

The principal, putting full faith in random sampling, plans to interview only the students numbered within some range , in increasing order of student number. To expedite the process, the principal will also set a threshold value . The first student blamed at least times will be expelled, concluding the investigation.

You want to anticipate various scenarios and determine the outcome for different sets of values for , , and . For each scenario, if a student would be expelled, output their number; otherwise, output `-1`

.

#### Constraints

##### Subtask 1 [25%]

##### Subtask 2 [75%]

No additional constraints.

#### Input Specification

The first line of input contains two integers and , the number of students and the number of scenarios respectively.

The second line of input contains integers , the student that the -th student blames.

The next lines each contain integers , the starting number, the ending number, and the threshold value picked by the principal in this scenario.

#### Output Specification

Output lines. The -th line should contain the answer to the -th scenario: the number of the student who would be expelled, or `-1`

if no such student exists.

#### Sample Input

```
10 6
3 2 3 1 1 7 7 10 9 2
1 7 1
6 10 3
4 6 1
4 10 5
3 10 1
5 10 2
```

#### Sample Output

```
3
-1
1
-1
3
7
```

#### Explanation for Sample

**In the second scenario:**

By the end of the principal's investigation, student would be blamed twice, and students , , and , would all be blamed once.

Since no one would be blamed at least times, no one would be expelled.

**In the sixth scenario:**

The principal would first interview student , who would blame student .

Next, the principal would interview student , who would blame student .

After, the principal would interview student , who would blame themself.

At this point, student would be blamed twice, thus the investigation would conclude with student being expelled.

## Comments