class Node:
    __slots__ = "l", "mid", "r", "lazy", "val", "left", "right"

    def __init__(self, l: int, r: int, val: int = 0, left: 'Node' = None, right: 'Node' = None):
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.val = val
        self.left = left
        self.right = right
        self.lazy = False

def push_up(node: 'Node'):
    node.val = node.left.val + node.right.val

def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # if node.lazy:
    #     xxxxxxxx

def build(node: 'Node'):
    if node.l == node.r:
        # node.val=xxxx
        return
    push_down(node)  # 开点
    build(node.left)
    build(node.right)
    push_up(node)

//继承前一个版本,使用它的子节点信息(old),但当前节点为新节点
    Node(Node *pre) {
        l = pre->l;
        r = pre->r;
        mid = pre->mid;
        left = pre->left;
        right = pre->right;
        cnt = pre->cnt + 1;//在前一个版本上区间里多加了一个点
    }

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"runtime/debug"
)

type T struct {
	val   int
	child [2]*T
	cnt   int
	size  int
	fa    *T
}

func NewT(val int, fa *T) *T {
	return &T{val: val, fa: fa, child: [2]*T{nil, nil}, cnt: 1, size: 1}
}
func (node *T) update() {
	node.size = node.cnt
	if node.child[0] != nil {
		node.size += node.child[0].size
	}
	if node.child[1] != nil {
		node.size += node.child[1].size
	}
}
func (node *T) idx() int {
	if node.fa != nil && node.fa.child[1] == node {
		return 1
	}
	return 0
}
func (node *T) rotate() {
	fa := node.fa
	if fa != nil {
		faf := fa.fa
		i := node.idx()
		if faf != nil {
			faf.child[fa.idx()] = node
		}
		node.fa = faf
		fa.child[i] = node.child[i^1]
		if node.child[i^1] != nil {
			node.child[i^1].fa = fa
		}
		fa.fa = node
		node.child[i^1] = fa
		fa.update()
		node.update()
	}
}
func (node *T) splay() *T {
	for node.fa != nil {
		if node.fa.fa != nil {
			if node.idx() == node.fa.idx() {
				node.fa.rotate()
			} else {
				node.rotate()
			}
		}
		node.rotate()
	}
	return node
}

type Splay struct {
	root *T
}

func NewSplay() *Splay {
	return &Splay{root: nil}
}
func (node *Splay) insert(val int) {
	if node.root == nil {
		node.root = NewT(val, nil)
		return
	}
	tmp := node.root
	for {
		if tmp.val == val {
			tmp.cnt++
			tmp.size++
			node.root = tmp.splay()
			return
		} else {
			i := 0
			if val > tmp.val {
				i = 1
			}
			if tmp.child[i] == nil {
				tmp.child[i] = NewT(val, tmp)
				tmp.update()
				node.root = tmp.splay()
				return
			} else {
				tmp = tmp.child[i]
			}
		}
	}
}
func (node *Splay) Get() (ans []int) {
	var dfs func(*T)
	dfs = func(t *T) {
		if t != nil {
			dfs(t.child[0])
			ans = append(ans, t.val)
			dfs(t.child[1])
		}
	}
	dfs(node.root)
	return
}

var (
	M    []int //映射,下标->value
	n, m int   //读入
)

// Node 线段树节点
type Node struct {
	l, mid, r, cnt int   //表示的区间范围
	left, right    *Node //左右子树
}

// NewNode 新节点
func NewNode(l int, r int) *Node {
	return &Node{l: l, r: r, mid: (l + r) >> 1, cnt: 0, left: nil, right: nil}
}

// Extend 新节点为继承了前一个版本的节点
func Extend(pre *Node) *Node {
	root := NewNode(pre.l, pre.r)
	root.cnt = pre.cnt + 1
	root.left = pre.left
	root.right = pre.right
	return root
}

// Build 第一个版本[l,r]都有点的树
func Build(node *Node) {
	if node.l == node.r {
		return
	}
	node.left = NewNode(node.l, node.mid)
	node.right = NewNode(node.mid+1, node.r)
	Build(node.left)
	Build(node.right)
}

// Add 往[x,x]添加一点,整体是开一条新链
func Add(pre *Node, x int) *Node {
	node := Extend(pre) //继承上一个版本的新节点
	if node.l == node.r {
		return node
	}
	//已经继承版本了,可以直接将自身子树作为pre
	if x <= node.mid {
		node.left = Add(node.left, x)
	} else {
		node.right = Add(node.right, x)
	}
	return node
}

// Query [l,r]上第k大的值
func (t *Seg) Query(l int, r int, k int) int {
	//在权值线段树上二分找到下标的size,使得前缀size和>=k(min)
	var binary func(*Node, *Node, int) int
	binary = func(left *Node, right *Node, i int) int {
		//如果遍历到了一个点,说明这个就是当前的下标
		if left.l == left.r {
			return left.l
		}
		//前缀和作差为当前区间的size总数,先看左半边区间
		diff := right.left.cnt - left.left.cnt
		//左半边区间,否则右半边区间,记得去掉左半边区间的数量,转为一个新的子问题
		if i <= diff {
			return binary(left.left, right.left, i)
		} else {
			return binary(left.right, right.right, i-diff)
		}
	}
	//类似前缀和作差sum[r]-sum[l-1]得到的就是[l,r]这个区间的所有线段树,M是下标从0开始的有序序列
	return M[binary(t.p[l-1], t.p[r], k)-1]
}

type Seg struct {
	h map[int]int //离散化 值=>下标
	p []*Node     //各个版本的根节点
}

func NewSeg(a []int) *Seg {
	h := make(map[int]int)
	var splay = NewSplay() //splay用于去重排序
	for _, v := range a {
		splay.insert(v)
	}
	M = splay.Get() //用于拿到整个有序序列
	for i, v := range M {
		h[v] = i + 1
	}
	var p = make([]*Node, len(a)+1)
	p[0] = NewNode(1, len(M))
	Build(p[0])
	for i, v := range a {
		p[i+1] = Add(p[i], h[v])
	}
	return &Seg{h, p}
}

func main() {
	debug.SetGCPercent(-1)
	Solve(os.Stdin, os.Stdout)
}

func Solve(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()
	//-----------------------------------------------------
	Fscan(in, &n, &m)
	var a = make([]int, n)
	for i := range a {
		Fscan(in, &a[i])
	}
	var seg = NewSeg(a)
	for m > 0 {
		m--
		var l, r, k int
		Fscan(in, &l, &r, &k)
		Fprintln(out, seg.Query(l, r, k))
	}
}

#![allow(unused_variables)]
#![warn(clippy::large_stack_arrays)]
#![warn(unused_macros)]

use crate::raw::in_out;
use crate::scanner::Scanner;
use std::io::{BufRead, Write};//----------------------------递归闭包---------------------------
// struct Func<'a, A, F>(&'a dyn Fn(Func<'a, A, F>, A) -> F);
//
// impl<'a, A, F> Clone for Func<'a, A, F> {
//     fn clone(&self) -> Self {
//         Self(self.0)
//     }
// }
//
// impl<'a, A, F> Copy for Func<'a, A, F> {}
//
// impl<'a, A, F> Func<'a, A, F> {
//     fn call(&self, f: Func<'a, A, F>, x: A) -> F {
//         (self.0)(f, x)
//     }
// }
//
// fn y<A, R>(g: impl Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R {
//     move |x| (|f: Func<A, R>, x| f.call(f, x))(Func(&|f, x| g(&|x| f.call(f, x), x)), x)
// }

//Y组合子使用示例:(多参采用元组传参)
// let dfs = | f: & dyn Fn((usize, i32,bool)) -> bool, (i,sum,s): (usize,i32,bool) | -> bool{
//      if i == n {
//          return sum == 0 & & s;
//       }
//      return f((i + 1, sum + a[i], true)) | | f((i + 1, sum, s)) | |
// f((i + 1, sum - a[i], true));
// };
//----------------------------递归闭包---------------------------
//----------------------------常用函数----------------------------
#[allow(dead_code)]
// #[inline]
fn prefix_array<T>(a: &Vec<T>, start: T) -> Vec<T> where T: std::ops::Add<Output=T> + Copy + std::ops::AddAssign {
    (0..=a.len()).scan(start, |x, y| if y == 0 { Some(start) } else {
        *x += a[y - 1];
        Some(*x)
    }).collect::<Vec<T>>()
}

#[allow(dead_code)]
// #[inline]
fn suffix_array<T>(a: &Vec<T>, end: T) -> Vec<T> where T: std::ops::Add<Output=T> + Copy + std::ops::AddAssign {
    let mut tmp = (0..=a.len()).rev().scan(end, |x, y| if y == a.len() { Some(end) } else {
        *x += a[y];
        Some(*x)
    }).collect::<Vec<T>>();
    tmp.reverse();
    tmp
}

#[allow(dead_code)]
extern "C" {
    fn getchar() -> i64;
}

#[allow(dead_code)]
fn next() -> i64 {
    let mut r = 0;
    let mut c;
    loop {
        unsafe { c = getchar(); }
        if c >= 48 && c < 48 + 10 { break; }
    }
    loop {
        r = r * 10 + c - 48;
        unsafe { c = getchar(); }
        if c < 48 || c >= 48 + 10 { break; }
    }
    r
}

//----------------------------常用函数----------------------------
//----------------------------Test----------------------------
const N: usize = 1000010;
static mut L: [i32; 25000250] = [0_i32; 25 * N];
static mut R: [i32; 25000250] = [0_i32; 25 * N];
static mut VAL: [i32; 25000250] = [0_i32; 25 * N];
//m次操作,每次多log(n)个数,可以适当开大不少,开到3e7级别
//分配节点
static mut ID: i32 = 0;
// //原数组
// static mut A: [i32; 1000010] = [0; N];
//根
static mut ROOT: Vec<i32> = vec![];

unsafe fn build(A: &Vec<i32>, l: i32, r: i32, curr: &mut i32) {
    if *curr == 0 {
        ID += 1;
        *curr = ID;
    }
    if l == r {
        VAL[*curr as usize] = A[l as usize];
        return;
    }
    let mid = (l + r) >> 1;
    build(A, l, mid, &mut L[*curr as usize]);
    build(A, mid + 1, r, &mut R[*curr as usize]);
}

unsafe fn update(pre: i32, curr: &mut i32, l: i32, r: i32, pos: i32, val: i32) {
    ID += 1;
    *curr = ID;
    L[*curr as usize] = L[pre as usize];
    R[*curr as usize] = R[pre as usize];
    if l == r {
        VAL[*curr as usize] = val;
        return;
    }
    let mid = (l + r) >> 1;
    if pos <= mid {
        update(L[pre as usize], &mut L[*curr as usize], l, mid, pos, val);
    } else {
        update(R[pre as usize], &mut R[*curr as usize], mid + 1, r, pos, val);
    }
}

unsafe fn query(curr: i32, l: i32, r: i32, pos: i32) -> i32 {
    if l == r {
        return VAL[curr as usize];
    }
    let mid = (l + r) >> 1;
    return if pos <= mid {
        query(L[curr as usize], l, mid, pos)
    } else {
        query(R[curr as usize], mid + 1, r, pos)
    };
}

//----------------------------Test----------------------------
// #[inline]
pub unsafe fn solve<R: BufRead, W: Write>(mut scanner: Scanner<R>, out: &mut W) {
    //---------------------------------------------常用宏---------------------------------------------
    #[allow(unused_macros)]
    macro_rules! puts {($($format:tt)*) => (let _ = writeln!(out,$($format)*););}
    #[allow(unused_macros)]
    macro_rules! r_usize {() => {scanner.next::<usize>()};}
    #[allow(unused_macros)]
    macro_rules! r_i32 {() => {scanner.next::<i32>()};}
    #[allow(unused_macros)]
    macro_rules! r_i64 {() => {scanner.next::<i64>()};}
    #[allow(unused_macros)]
    macro_rules! r_i128 {() => {scanner.next::<i128>()};}
    #[allow(unused_macros)]
    macro_rules! r_isize {() => {scanner.next::<isize>()};}
    #[allow(unused_macros)]
    macro_rules! r_s_u8 {() => {scanner.next::<String>().into_bytes()};}
    #[allow(unused_macros)]
    macro_rules! read_usize {($n:expr) => {(0..$n).map(|_|scanner.next::<usize>()).collect::<Vec<usize>>()};}
    #[allow(unused_macros)]
    macro_rules! read_i32 {($n:expr) => {(0..$n).map(|_|scanner.next::<i32>()).collect::<Vec<i32>>()};}
    #[allow(unused_macros)]
    macro_rules! read_i64 {($n:expr) => {(0..$n).map(|_|scanner.next::<i64>()).collect::<Vec<i64>>()};}
    #[allow(unused_macros)]
    macro_rules! read_i128 {($n:expr) => {(0..$n).map(|_|scanner.next::<i128>()).collect::<Vec<i128>>()};}
    #[allow(unused_macros)]
    macro_rules! read_tow_array_usize {($n:expr,$m:expr) => {(0..$n).map(|_|read_usize!($m)).collect::<Vec<Vec<usize>>>()};}
    #[allow(unused_macros)]
    macro_rules! read_tow_array_i32 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i32!($m)).collect::<Vec<Vec<i32>>>()};}
    #[allow(unused_macros)]
    macro_rules! read_tow_array_i64 {($n:expr,$m:expr) => {(0..$n).map(|_|read_i64!($m)).collect::<Vec<Vec<i64>>>()};}
    #[allow(unused_macros)]
    macro_rules! count_bit {($n:expr) => {{let(mut ans,mut k)=(0_usize,$n);while k>0{ans+=1;k&=k-1;}ans}};}
    #[allow(unused_macros)]
    macro_rules! print_all {($A:expr) => {{for &v in &$A{let _ = write!(out, "{} ", v);}puts!();}};}
    //-----------------------------------------------------------------------------------------------
    let n = r_usize!();
    let m = r_usize!();
    let mut A = vec![0; n + 1];
    for i in 1..=n {
        A[i] = scanner.next::<i32>();
    }
    ROOT.push(0);
    build(&A, 1, n as i32, &mut ROOT[0]);
    for i in 1..=m {
        ROOT.push(0);
        let v = r_i32!();//版本号
        if r_usize!() == 1 {
            let pos = r_i32!();
            let val = r_i32!();
            update(ROOT[v as usize], &mut ROOT[i], 1, n as i32, pos, val);
        } else {
            let pos = r_i32!();
            puts!("{}",query(ROOT[v as usize],1,n as i32,pos));
            ROOT[i] = ROOT[v as usize];
        }
    }
}

//-----------------------------main-------------------------------------
fn main() {
    let (stdin, mut stdout) = in_out();
    unsafe { solve(Scanner::new(stdin), &mut stdout); }
}

// --------------------------- tools -----------------------------------
mod raw {
    use std::fs::File;
    use std::io::{BufRead, BufReader, BufWriter, stdin, stdout, Write};


    #[cfg(windows)]
    pub fn in_out() -> (impl BufRead, impl Write) {
        use std::os::windows::prelude::{AsRawHandle, FromRawHandle};
        unsafe {
            let stdin = File::from_raw_handle(stdin().as_raw_handle());
            let stdout = File::from_raw_handle(stdout().as_raw_handle());
            (BufReader::new(stdin), BufWriter::new(stdout))
        }
    }

    #[cfg(unix)]
    pub fn in_out() -> (impl BufRead, impl Write) {
        use std::os::unix::prelude::{AsRawFd, FromRawFd};
        unsafe {
            let stdin = File::from_raw_fd(stdin().as_raw_fd());
            let stdout = File::from_raw_fd(stdout().as_raw_fd());
            (BufReader::new(stdin), BufWriter::new(stdout))
        }
    }
}

mod scanner {
    use std::io::BufRead;

    pub struct Scanner<R> {
        reader: R,
        buf_str: Vec<u8>,
        buf_iter: std::str::SplitAsciiWhitespace<'static>,
    }

    impl<R: BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Self { reader, buf_str: Vec::new(), buf_iter: "".split_ascii_whitespace() }
        }
        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            loop {
                if let Some(token) = self.buf_iter.next() {
                    return token.parse().ok().expect("Failed parse");
                }
                unsafe { self.buf_str.set_len(0); }
                self.reader.read_until(b'\n', &mut self.buf_str).expect("Failed read");
                self.buf_iter = unsafe {
                    let slice = std::str::from_utf8_unchecked(&self.buf_str);
                    std::mem::transmute(slice.split_ascii_whitespace())
                }
            }
        }
    }
}