1628 - LowerBound

Time Limit: 1s Memory Limit: 128MB

Submissions: 123 Solved: 49
Description
You are given a sequence A[1], A[2],  ..., A[N]  . (  |A[i]| ≤ 2*10^9, 1 ≤ N ≤ 100000 ). A query is defined as follows: 
(L,R,V) : find the smallest number of A[i] such that L<=i<=R and A[i]>V, if not exist, output 
“not exist”.
Given M queries, your program must output the results of these queries.
Input
The first line contains a single integer T, the number of test cases.
For each case, there are two integers N and M (1<= N, M <=100000).
The next line contain N elements.
A1 A2 … AN
The next M lines contain the operation in following form.
L1 R1 V1
L2 R2 V2
LM RM VM
Output
For each question, output the answer in one line.
Sample Input
1
5 5
5 4 3 2 1
1 5 2
2 4 0
3 5 3
1 4 3
2 5 1
Sample Output
3
2
not exist
4
2
Hint
Source
The 8th(2013) ACM Programming Contest of HUST