C. Not Equal on a Segmenttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.InputThe first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.OutputPrint m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value  - 1 if there is no such number.ExamplesInput6 41 2 1 1 3 51 4 12 6 23 4 13 4 2Output26-14
Input6 41 2 1 1 3 51 4 12 6 23 4 13 4 2
Output26-14
['data structures', 'implementation', '*1700']