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

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

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

Constraints

$1\le N,Q\le 5\times {10}^5$

$1\le A_i\le N$

$1\le l\le r\le N$

$1\le k\le N$

Subtask 1 [25%]

$1\le k\le 50$

Subtask 2 [75%]

No additional constraints.

Input Specification

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

The second line of input contains $N$ integers $A_1,A_2,\dots ,A_N$, the student that the $i$-th student blames.

The next $Q$ lines each contain $3$ integers $l,r,k$, the starting number, the ending number, and the threshold value picked by the principal in this scenario.

Output Specification

Output $Q$ lines. The $i$-th line should contain the answer to the $i$-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 $7$ would be blamed twice, and students $2$, $9$, and $10$, would all be blamed once.

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

In the sixth scenario:

The principal would first interview student $5$, who would blame student $1$.

Next, the principal would interview student $6$, who would blame student $7$.

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

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