题目描述

给定长度为$n$的序列$a_i$，以及$m$个操作。 操作一：1 x k，将$a_x$赋值为$k$； 操作二：2 x，询问在所有数中，第$x$小的数是几。 其中，第$x$小的数是指，如果将所有数从小到大排序，排在第$x$个的数。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 接下来$m$行，每行输入一个操作，格式如题面所示。

输出格式

对于每次询问操作，输出一行一个整数，表示你的答案。

样例输入 #1

5 5
5 4 3 2 1
2 4
1 2 6
2 4
1 1 7
2 4

样例输出 #1

4
5
6

说明/提示

保证$1\leq n,m,a_i,k\leq 10^5,1\leq x\leq n$。