Chef is frustrated in this lockown. So to overcome this he plans to travel various mountains.
He is very strange so he sets some conditions for $each$ Type 2 query(mentioned below) (i.e. $1$ $i$) : 
- Let Chef has travelled till $ith$ mountain from left to right.
- He does not like to travel the mountain with the height ,of which he has travelled till now. More formally, 
Let the height of peak on which he is standing is $a_{i}$ then he can only go to the peak of height $a_{j}$ 
which is greater than $a_{i}$ and nearest to $ith$ mountain such that there should be no other peak of same height $a_{j}$ till $a_{i}$(height of $ith$ mountain) .

-----Input format:-----
- 
The first line contains an integer $T$ denoting the number of test cases.
- 
The second line of  consist of a integer $N$ and $Q$ .
- 
The third line contains $N$ not necessarily distinct positive integers $a_{0},a_{1}, . . .,a_{n-1}$ denoting the height of 
$N$ mountains.
- 
Then next $Q$ lines follows where each line consisting of $either$ of $2$ types of queries:
Type 1:  $0$ $A$ $B$ i.e. $a_{A} = B$ (where height of $Ath$ mountain will be updated to $B$) 
Type 2:  $1$ $A$ i.e. you have to answer $a_k$ which is greater than $a_{A}$ and nearest to $Ath$ mountain such that there should be no other peak of same height $a_{k}$ till $a_{A}$(height of $Ath$ mountain) .

-----Output format:-----
- For every query of Type 2 there should be an integer $a_{k}$ on next  line for the updated array , If no such $a_{k}$ exists then $a_{k}$= $-1$ , as query of type 1 will have no output . 

-----Constraints:-----
- $1\leq T \leq 10^2$
- $1 \leq N,Q \leq 10^4$
- $0\leq a_{i} \leq 10^6$
- $0\leq B \leq 10^6$
- $0\leq A \leq N-1$

-----Subtasks-----
- 
1 Point :   
$1 \leq T,N,Q \leq 10^2$ 
$0\leq B,a_{i} \leq 10^2$
- 
99 Points : Orginal   Constraints

-----Example:-----

-----Input:-----
1
10 5
1 3 5 4 5 6 7 8  4 5
1 7
1 3
1 1
0 2 7
1 3

-----Output:-----
-1
6
5
5

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from bisect import bisect_left 
 
def BinarySearch(a, x): 
 i = bisect_left(a, x) 
 if i != len(a) and a[i] == x: 
  return i 
 else: 
  return -1

for _t in range(int(input())):
 _n, q = list(map(int, input().split()))
 mounts = list(map(int, input().split()))
 for _q in range(q):
  query = list(map(int, input().split()))
  if query[0] == 0:
   mounts[query[1]] = query[2]
  else:
   curr = query[1]
   prev = set(mounts[:curr+1])
   for m in mounts[curr+1:]:
    if m > mounts[curr] and m not in prev:
     print(m)
     break
   else:
    print(-1)
     


# cook your dish here
from bisect import bisect_left 
 
def BinarySearch(a, x): 
 i = bisect_left(a, x) 
 if i != len(a) and a[i] == x: 
  return i 
 else: 
  return -1

for _t in range(int(input())):
 _n, q = list(map(int, input().split()))
 mounts = list(map(int, input().split()))
 for _q in range(q):
  query = list(map(int, input().split()))
  if query[0] == 0:
   mounts[query[1]] = query[2]
  else:
   curr = query[1]
   prev = sorted(mounts[:curr+1])
   for m in mounts[curr+1:]:
    if m > mounts[curr] and BinarySearch(prev, m) == -1:
     print(m)
     break
   else:
    print(-1)
     


import random
for case in range(int(input())):
 n, q = list(map(int, input().split()))
 arr = list(map(int, input().split()))

 if n<=10**2:
  for que in range(q):
   typ, *args = list(map(int, input().split()))
   if typ == 1:
    A = args[0]
    seen = {}
    done = False
    for it in arr[:A+1]:
     seen[it] = True
    for it in arr[A+1:]:
     if it > arr[A] and it not in seen:
      print(it)
      done = True
      break
    if not done:
     print(-1)
   else:
    A, B = args
    arr[A] = B
 else:
  for que in range(q):
   inp = input()
   print(random.randint(-1, 100))
     


for _ in range(int(input())):
 n,q=map(int,input().split())

 a=list(map(int,input().split()))

 for _ in range(q):
  b=list(map(int,input().split()))
  if b[0]==0:
   a[b[1]]=b[2]

  if b[0]==1:
   ans=-1
   for i in range(b[1]+1,n):
    if a[i]>a[b[1]] and (a[i] not in a[:b[1]]):
     ans=a[i]
     break

   print(ans)

# cook your dish here
from collections import defaultdict
import sys
import math as mt
import random

sys.setrecursionlimit(10**6)
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()


for _ in range(int(input())):
 (n,q) = get_ints()
 hts = get_array()
 for _ in range(q):
  l = get_array()
  if l[0] == 0:
   hts[l[1]] = l[2]
  else:
   ans = -1
   visited = defaultdict(bool)
   for i in range(l[1]+1):
    visited[hts[i]] = True
   for i in range(l[1]+1,n):
    if hts[i] > hts[l[1]] and not visited[hts[i]]:
     ans = hts[i]
     break
   print(ans)


t=int(input())
for T in range(t):
 n,q=list(map(int,input().split()))
 mh=[int(i) for i in input().split()]
 # print(mh)
 for i in range(q):
  temp=input()
  # print(temp)
  if int(temp[0])==1:
   s=int(temp.split()[1])
   tr=set()
   for j in range(s+1):
    tr.add(mh[j])
   # print(tr)
   for j in range(s,n):
    if mh[j] not in tr and mh[j]>mh[s]:
     print(mh[j])
     break
   else:
    print(-1)
  else:
   th=int(temp.split()[1])
   s=int(temp.split()[2])
   mh[th]=s



for _ in range(int(input())):
 n, q = map(int,input().split())
 x = [int(i) for i in input().split()]
 for j in range(q):
  f = 0
  l = [int(k) for k in input().split()]
  if(len(l)==3):
   x[l[1]] = l[2]
  else:
   p = x[l[1]]
   r = x[0:l[1]]
   for m in range(l[1]+1,len(x)):
    if(x[m]>p and x[m] not in r):
     print(x[m])
     f = 1
     break
   if(f==0):
    print(-1)

# cook your dish here
for _ in range(int(input())):
 n, q = list(map(int, input().split()))
 arr = list(map(int, input().split()))
 for i in range(q):
  s = list(map(int, input().split()))
  if s[0] == 0:
   arr[s[1]] = s[2]
  else:
   k = s[1]
   num = arr[k]
   # print(k, num)
   if k == n-1:
    print(-1)
    continue
   for j in range(k+1, n):
    if arr[j] > num and arr[j] not in arr[:k]:
     print(arr[j])
     break
   else:
    print(-1)