A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. Now, being the geek that you are, you thought of the following two queries which can be performed on these shelves.

Change the number of books in one of the shelves.

Obtain the number of books on the shelf having the$ k^{th}$ rank within 
the range of shelves. 

A shelf is said to have the $k^{th} $rank if its position is k when the shelves are sorted based on the number of the books they contain, in ascending order.

Can you write a program to simulate the above queries?

Input Format 

The first line contains a single integer T, denoting the number of test cases. 

The first line of each test case contains an integer N denoting the number of shelves in the library. 

The next line contains N space separated integers where the$ i^{th} $integer represents the number of books on the$ i^{th}$ shelf where 1<=i<=N. 

The next line contains an integer Q denoting the number of queries to be performed. Q lines follow with each line representing a query. 

Queries can be of two types:

1 x k - Update the number of books in the $x^{th}$ shelf to k (1 <= x <= N).
0 x y k - Find the number of books on the shelf between the shelves x and y 
(both inclusive) with the$ k^{th}$ rank (1 <= x <= y <= N, 1 <= k <= y-x+1).

Output Format 

For every test case, output the results of the queries in a new line.

Constraints 

1 <= T <= 5 

1 <= N <=$ 10^{4}$ 

1 <= Q <= $10^{4} $

The number of books on each shelf is always guaranteed to be between 1 and 1000.

Sample Input

2
2
1 2
2
0 1 2 1
0 1 2 2
4
4 3 2 1
4
0 1 1 1
1 1 1
0 1 1 1
0 1 4 3

Sample Output

1
2
4
1
2

Explanation  

There are two test cases :

The first test case contains only two shelves which can be represented as [1, 2]. Two queries are to be processed : 

i) The first query asks for smallest number of books between the $1^{st} $and$ 2^{nd}$ shevles which is 1.  

ii) The second query asks for the $2^{nd}$ smallest number of books between the$1^{st}$ and$ 2^{nd} $shevles which is 2.  

The second test case contains four shelves which can be represented as [4, 3, 2, 1]. Four queries are to be processed :  

i) The first query asks for the smallest number of books in the$ 1^{st}$ shelf which is 4.  

ii) The second query updates the number of books in the $1^{st}$ shelf to 1. Hence the shelves now look like [1, 3, 2, 1].  

iii) The third query asks for the smallest number of books in the $1^{st} $shelf which is now 1.  

iv) The last query asks for the $3^{rd} $smallest number of books between the $1^{st}$ and $4^{th}$ shelves which is 2.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


def query(C, a, b, r):
	S = [0] * 1001
	for c in C[a:b + 1]:
		S[c] += 1
	total = 0
	for (i, s) in enumerate(S):
		total += s
		if total >= r:
			return i
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	C = [int(c) for c in input().strip().split(' ')]
	q = int(input().strip())
	for _ in range(q):
		qry = input().strip()
		if qry.startswith('0'):
			(x, y, k) = [int(w) for w in qry.split(' ')[1:]]
			print(query(C, x - 1, y - 1, k))
		elif qry.startswith('1'):
			(x, k) = [int(w) for w in qry.split(' ')[1:]]
			C[x - 1] = k
		else:
			raise ValueError('Invalid query type')


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


import array

class FTree2D:
	LSB = lambda n: n & -n

	def __init__(self, sizerow, sizecol):
		self.sizerow = sizerow
		self.sizecol = sizecol
		(rowinc, colinc) = (sizerow + 1, sizecol + 1)
		self.buf = memoryview(bytearray(2 * rowinc * colinc)).cast('H', (rowinc, colinc))

	def add(self, i, val):
		x = i[0]
		while x <= self.sizerow:
			y = i[1]
			while y <= self.sizecol:
				self.buf[x, y] += val
				y += FTree2D.LSB(y)
			x += FTree2D.LSB(x)

	def set(self, i, val):
		self.add(i, val - self.get(i))

	def get(self, i):
		return self.sum_part(i, i)

	def sum_full(self, i):
		sum = 0
		x = i[0]
		while x:
			y = i[1]
			while y:
				sum += self.buf[x, y]
				y ^= FTree2D.LSB(y)
			x ^= FTree2D.LSB(x)
		return sum

	def sum_part(self, first, last):
		(x0, x1) = sorted((first[0], last[0]))
		(y0, y1) = sorted((first[1], last[1]))
		(x0, y0) = (x0 - 1, y0 - 1)
		return +self.sum_full((x1, y1)) - self.sum_full((x0, y1)) - self.sum_full((x1, y0)) + self.sum_full((x0, y0))

def solve(shelves, queries):
	MAX_BOOKS = 1000
	results = []
	ft = FTree2D(len(shelves), MAX_BOOKS)
	for (idx, shelfsize) in enumerate(shelves, 1):
		ft.add((idx, shelfsize), 1)
	for query in queries:
		(op, *args) = map(int, query.split())
		if op == 0:
			(first, last, k) = args
			shelf_count = lambda size: ft.sum_full((last, size)) - ft.sum_full((first - 1, size))
			(lo, hi) = (1, MAX_BOOKS)
			if shelf_count(lo) >= k:
				results.append(lo)
			else:
				while True:
					pivot = (lo + hi) // 2
					if pivot == lo:
						break
					if shelf_count(pivot) >= k:
						hi = pivot
					else:
						lo = pivot
				results.append(hi)
		elif op == 1:
			(idx, shelfsize) = args
			ft.add((idx, shelves[idx - 1]), -1)
			shelves[idx - 1] = shelfsize
			ft.add((idx, shelfsize), 1)
		else:
			raise RuntimeError('query with unknown op-code')
	return results
T = int(input())
for _ in range(T):
	input()
	shelves = list(map(int, input().split()))
	Q = int(input())
	queries = []
	for q in range(Q):
		queries.append(input())
	print('\n'.join(map(str, solve(shelves, queries))))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class BinaryIndexedTree2D:

	def __init__(self, max_x=10000):
		self.x_max = 10000
		self.y_max = 1000
		self.tree = [[0 for i in range(self.y_max + 5)] for j in range(self.x_max + 5)]

	def update(self, x, y, val):
		while x <= self.x_max:
			y1 = y
			while y1 <= self.y_max:
				self.tree[x][y1] += val
				y1 += y1 & -y1
			x += x & -x

	def getFrequency(self, x, y):
		sum_ = 0
		while x > 0:
			y1 = y
			while y1 > 0:
				sum_ += self.tree[x][y1]
				y1 -= y1 & -y1
			x -= x & -x
		return sum_

def solve(t, l, r, k):
	low = 1
	high = t.y_max
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		v2 = t.getFrequency(r, mid)
		v1 = t.getFrequency(l - 1, mid)
		if v2 - v1 >= k:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	return ans
s = ''
for _ in range(int(input())):
	n = int(input())
	tree = BinaryIndexedTree2D(n)
	no_books = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		tree.update(i, no_books[i], 1)
	q = int(input())
	for i in range(q):
		query = list(map(int, input().split()))
		t = query[0]
		if t == 0:
			(x, y, k) = query[1:]
			res = solve(tree, x, y, k)
			s += str(res) + '\n'
		else:
			(x, k) = query[1:]
			tree.update(x, no_books[x], -1)
			no_books[x] = k
			tree.update(x, no_books[x], 1)
print(s)


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))


class FenwickTree2D:

	def __init__(self, x, y):
		self.size_x = x
		self.size_y = y
		self.data = [[0] * self.size_y for _ in range(self.size_x)]

	def sum(self, x1, y1):
		if min(x1, y1) <= 0:
			return 0
		s = 0
		x = x1
		while x >= 0:
			y = y1
			while y >= 0:
				s += self.data[x][y]
				y = (y & y + 1) - 1
			x = (x & x + 1) - 1
		return s

	def sumrange(self, x1, y1, x2, y2):
		return self.sum(x2, y2) - self.sum(x1 - 1, y2) - self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1)

	def add(self, x1, y1, w):
		assert min(x1, y1) > 0
		x = x1
		while x < self.size_x:
			y = y1
			while y < self.size_y:
				self.data[x][y] += w
				y |= y + 1
			x |= x + 1
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	t = FenwickTree2D(10001, 1001)
	for i in range(len(arr)):
		t.add(i + 1, arr[i], 1)
	Q = int(input())
	for q in range(Q):
		c = list(map(int, input().split()))
		if c[0] == 1:
			t.add(c[1], arr[c[1] - 1], -1)
			arr[c[1] - 1] = c[2]
			t.add(c[1], arr[c[1] - 1], 1)
		else:

			def select(l, r, k):
				(lo, hi) = (1, 1000)
				while lo < hi:
					med = (hi + lo) // 2
					a = t.sumrange(l, 0, r, med)
					if a >= k:
						hi = med
					else:
						lo = med + 1
				if not t.sumrange(l, 0, r, lo) >= k:
					raise ValueError
				return lo
			print(select(c[1], c[2], c[3]))