using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Reflection.Emit;
using System.Runtime.InteropServices.Marshalling;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Linq;
using Microsoft.VisualBasic;


namespace test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            cin = new input();
            //mod = new mod(998244353);
            //toolbox = new toolbox();
            //Priority_Queue = new Priority_Queue(true);
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            //toolbox.StartTimer();
            var time=new Stopwatch();
            time.Start();

            int n = cin.intreed();
            int q = cin.intreed();
            var arr = new List<long>();
            arr.Add(0);
            for (int i = 1; i <= n; i++)
            {
                arr.Add(cin.longreed());
            }
            var tree=new AvlMultiset();
            bool sorted = false;//1度でもソートされたか
            var changed = Enumerable.Range(1, n).ToList();
            var changedFlag = new bool[n + 1];
            Array.Fill(changedFlag, true);
            changedFlag[0] = false;

            while (q-- > 0)
            {
                int mode = cin.intreed();
                if (mode == 1)
                {
                    int k = cin.intreed();//k番目の値が更新される
                    long x = cin.longreed();
                    arr[k]=x;
                    if(!changedFlag[k])
                    {
                        changedFlag[k]=true;
                        changed.Add(k);
                    }
                }
                else if (mode == 2)
                {
                    if(changed.Count==0)
                        continue;
                    changed.Sort();
                    if(!sorted)
                    {
                        foreach(var k in changed)
                        {
                            tree.Insert(arr[k]);
                            changedFlag[k]=false;
                        }
                        changed.Clear();
                        sorted=true;
                        continue;
                    }

                    int removed=0;
                    foreach(var k in changed)
                    {
                        int target=k-removed;
                        long val=tree[target];
                        tree.Erase(val);
                        removed++;
                    }
                    foreach(var k in changed)
                    {
                        tree.Insert(arr[k]);
                        changedFlag[k]=false;
                    }
                    changed.Clear();
                }
                else
                {
                    int k = cin.intreed();
                    if (changedFlag[k])
                    {
                        System.Console.WriteLine(arr[k]);
                    }
                    else
                    {
                        System.Console.WriteLine(tree[k]);
                    }
                }
            }
            Console.Error.WriteLine(time.ElapsedMilliseconds);
            //toolbox.PrintElapsedTime();
            Console.Out.Flush();
        }
        static input cin;
        //static mod mod;
        //static toolbox toolbox;
        //static Priority_Queue Priority_Queue;
    }
    
    public class AvlMultiset
    {
        //1-indexです!!!!!!
        private class node
        {
            public long val;
            public int cnt;//同じ値の個数
            public int height;
            public int size;//部分木内の要素数（cnt含む）
            public node left;
            public node right;

            public node(long v)
            {
                val = v;
                cnt = 1;
                height = 1;
                size = 1;
            }
        }

        private node root;
        private static int Height(node t) => t?.height ?? 0;
        private static int Size(node t) => t?.size ?? 0;

        private static void Update(node t)
        {
            if (t == null) return;
            t.height = Math.Max(Height(t.left), Height(t.right)) + 1;
            t.size = Size(t.left) + Size(t.right) + t.cnt;
        }

        private static int BalanceFactor(node t) => Height(t.left) - Height(t.right);

        private static node RotateRight(node y)
        {
            var x = y.left;
            var t2 = x.right;
            x.right = y;
            y.left = t2;
            Update(y);
            Update(x);
            return x;
        }

        private static node RotateLeft(node x)
        {
            var y = x.right;
            var t2 = y.left;
            y.left = x;
            x.right = t2;
            Update(x);
            Update(y);
            return y;
        }

        private static node Balance(node t)
        {
            if (t == null) return null;
            Update(t);
            int bf = BalanceFactor(t);
            if (bf > 1)
            {
                if (BalanceFactor(t.left) < 0)
                {
                    t.left = RotateLeft(t.left);
                }
                return RotateRight(t);
            }
            if (bf < -1)
            {
                if (BalanceFactor(t.right) > 0)
                {
                    t.right = RotateRight(t.right);
                }
                return RotateLeft(t);
            }
            return t;
        }

        private node Insert(node t, long val)
        {
            if (t == null) return new node(val);
            if (val < t.val)
            {
                t.left = Insert(t.left, val);
            }
            else if (val > t.val)
            {
                t.right = Insert(t.right, val);
            }
            else
            {
                t.cnt++;
                Update(t);
                return t;
            }
            return Balance(t);
        }

        private node RemoveMin(node t, out node removed)
        {
            if (t.left == null)
            {
                removed = t;
                var right = t.right;
                t.left = null;
                t.right = null;
                return right;
            }
            t.left = RemoveMin(t.left, out removed);
            return Balance(t);
        }

        private node Erase(node t, long val)
        {
            if (t == null) return null;
            if (val < t.val)
            {
                t.left = Erase(t.left, val);
            }
            else if (val > t.val)
            {
                t.right = Erase(t.right, val);
            }
            else
            {
                if (t.cnt > 1)
                {
                    t.cnt--;
                    return Balance(t);
                }
                if (t.left == null) return t.right;
                if (t.right == null) return t.left;

                t.right = RemoveMin(t.right, out var successor);
                successor.left = t.left;
                successor.right = t.right;
                t = successor;
            }
            return Balance(t);
        }

        private bool Find(node t, long val)
        {
            while (t != null)
            {
                if (val < t.val) t = t.left;
                else if (val > t.val) t = t.right;
                else return true;
            }
            return false;
        }

        private long GetKth(node t, int k)
        {
            if (t == null || k < 1 || k > Size(t))
                throw new ArgumentOutOfRangeException(nameof(k));

            int leftCount = Size(t.left);
            if (k <= leftCount)
            {
                return GetKth(t.left, k);
            }
            if (k <= leftCount + t.cnt)
            {
                return t.val;
            }
            return GetKth(t.right, k - leftCount - t.cnt);
        }

        //外部向け
        public void Insert(long val) => root = Insert(root, val);

        public void Erase(long val) => root = Erase(root, val);

        public bool Find(long val) => Find(root, val);

        public int Count() => Size(root);

        public long this[int index] => GetKth(root, index);
    }

    internal class input
    {
        string[] soloinput;
        int t;
        public input()
        {
            soloinput = new string[0];
            t = 0;
        }
        public string soloreed()
        {
            if (t < soloinput.Length)
            {
                return soloinput[t++];
            }
            string input = Console.ReadLine();
            while (input == "")
            {
                input = Console.ReadLine();
            }
            soloinput = input.Split(" ");
            t = 0;
            return soloinput[t++];
        }
        public int intreed()
        {
            return int.Parse(soloreed());
        }
        public int[] arrayint(int N)
        {
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = intreed();
            }
            return A;
        }
        public long longreed()
        {
            return long.Parse(soloreed());
        }
        public long[] arraylong(long N)
        {
            long[] A = new long[N];
            for (long i = 0; i < N; i++)
            {
                A[i] = longreed();
            }
            return A;
        }
        public decimal decimalreed()
        {
            return decimal.Parse(soloreed());
        }
        public decimal[] arraydecimal(long N)
        {
            decimal[] A = new decimal[N];
            for (decimal i = 0; i < N; i++)
            {
                A[(long)i] = decimalreed();
            }
            return A;
        }


    }

}