I. Fire Fighters
time limit per test
3.3 seconds
memory limit per test
333 megabytes
input
standard input
output
standard output

In Fireland, there are $$$n$$$ fires placed in a line fighting in a tournament, and the $$$i$$$-th fire has a power of $$$a_{i}$$$.

The tournament works as follows: If there are at least two fires remaining, the first two fires will fight.

When two fires with powers $$$x$$$ and $$$y$$$ fight, only three options can happen:

$$$1$$$ If $$$x$$$ $$$ \gt $$$ $$$y$$$, $$$y$$$ becomes disqualified.

$$$2$$$ If $$$x$$$ $$$ \lt $$$ $$$y$$$, $$$x$$$ becomes disqualified.

$$$3$$$ If $$$x$$$ $$$=$$$ $$$y$$$, both become disqualified.

Your task is to answer $$$q$$$ independent queries of the form:

Given $$$l$$$, $$$r$$$ and $$$x$$$, you have to find the index of the tournament's winner if each value in the range $$$[l, r]$$$ becomes changed to $$$x$$$, or report that nobody wins.

Check the sample explanations for a better understanding of the problem.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 69)$$$. The description of the test cases follows.

The first line consists of two integers $$$n$$$ $$$(2 \leq n, q \leq 6.9 \cdot 10^{5})$$$ $$$-$$$ the number of fires and the number of queries, respectively.

Then follows $$$n$$$ integers $$$a_{i}$$$ $$$(-6.9 \cdot 10^{8} \leq a_{i} \leq 6.9 \cdot 10^{8})$$$ $$$-$$$ the fires powers.

The last $$$q$$$ lines consist of three integers $$$l$$$, $$$r$$$ and $$$x$$$ $$$(1 \leq l \leq r \leq n ; -6.9 \cdot 10^{8} \leq x \leq 6.9 \cdot 10^{8})$$$ $$$-$$$ the values of the queries.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{5}$$$.

—

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Tests $$$1-3$$$: $$$(2 \leq n, q \leq 6.9 \cdot 10^{3})$$$ and it is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{3}$$$.

Tests $$$4-6$$$: $$$(2 \leq n, q \leq 6.9 \cdot 10^{4})$$$ and it is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{4}$$$.

Tests $$$7-20$$$: No additional constraints.

Each test is worth 5 points with samples skipped.

Output

For each query, you have to output the index of the tournament's winner. If nobody wins the tournament, the answer is $$$n+1$$$.

Example
Input
2
5 5
1 2 1 4 3
1 1 6
4 4 3
2 3 4
1 3 5
2 4 3
2 2
-1 -2
1 1 -1
1 2 0
Output
1
6
4
3
6
1
3
Note

For the first test case:

The answer to the first query is $$$1$$$ because the fire on position $$$1$$$ has the unique biggest power.

The answer to the third query is $$$4$$$ because the first fire loses against the second one, and when the second and the third fire fight, they both become disqualified. Finally, the fourth fire wins the fifth one and becomes the tournament's winner.

For the second test case:

The answer to the second query is $$$3$$$ because if $$$a_{0}$$$ and $$$a_{1}$$$ are equal, when they fight they both become disqualified.

—

Problem Idea: danx

Problem Preparation: danx

Occurrences: Advanced 9