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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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)


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)


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()]
	for i in range(q):
		temp = input()
		if int(temp[0]) == 1:
			s = int(temp.split()[1])
			tr = set()
			for j in range(s + 1):
				tr.add(mh[j])
			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)


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]
			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)