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, \ldots, 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.