using System.Diagnostics;
using System.Reflection.Emit;
using System.Runtime.InteropServices.Marshalling;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
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>();//1indexにしておく
            arr.Add(0);
            for (int i = 1; i <= n; i++)
            {
                arr.Add(cin.longreed());
            }
            Treap.node root=null;
            var treapRand=new Random(998244353);
            bool sorted = false;//1度でもソートされたか
            var changed=Enumerable.Range(1,n).ToList();
            var changed_bool=new bool[n+1];
            var diff=new long[n+1];
            for (int i = 1; i <= n; i++)
            {
                diff[i]=arr[i];
            }


            while (q-- > 0)
            {
                int mode = cin.intreed();
                if (mode == 1)
                {
                    int k = cin.intreed();//k番目の値が更新される
                    long x = cin.longreed();
                    diff[k]=x;
                    changed.Add(k);
                    changed_bool[k]=true;
                }
                else if (mode == 2)
                {
                    var remove = new List<long>();
                    if (sorted)
                    {
                        foreach (var k in changed)
                        {
                            remove.Add(Treap.GetKth(root,k));//k番目の要素は削除する
                        }
                        foreach (var i in remove)
                            Treap.Erase(ref root,i);
                    }
                    foreach (var k in changed)
                    {
                        Treap.Insert(ref root,diff[k],treapRand);
                        changed_bool[k]=false;
                    }
                    changed.Clear();
                    sorted = true;
                }
                else
                {
                    int k = cin.intreed();
                    if (changed_bool[k])
                    {
                        System.Console.WriteLine(diff[k]);
                    }
                    else
                    {
                        System.Console.WriteLine(Treap.GetKth(root,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 static class Treap
    {
        //1-indexです!!!!!!
        public class node
        {
            public long val;
            public node left;//小さい
            public node right;//大きい
            public int cnt;//部分木の大きさ
            public int priority;//優先度

            public node(long val, int priority, node left = null, node right = null)
            {
                this.val = val;
                this.priority = priority;
                this.left = left;
                this.right = right;
            }

            public long update()
            {
                cnt = 1;
                if (left != null) cnt += left.cnt;
                if (right != null) cnt += right.cnt;
                return cnt;
            }
        }

        //key未満のノードとkey以上のノードに分割する
        private static void Split(node t, long key, out node left, out node right)
        {
            if (t == null)
            {
                left = null;
                right = null;
                return;
            }
            else if (key <= t.val)
            {
                //key以上なので、今回のノードと右側部分木は右に行く
                Split(t.left, key, out left, out t.left);
                right = t;
            }
            else
            {
                //key未満なので、今回のノードと右側部分木は右に行く
                Split(t.right, key, out t.right, out right);
                left = t;
            }

            t.update();
        }

        //左と右を合体した新たな木(t)を作る
        private static void Marge(ref node t, node left, node right)
        {
            if (left == null || right == null)
            {
                t = left ?? right;
            }
            else if (left.priority > right.priority)
            {
                //leftの方が優先度高い
                Marge(ref left.right, left.right, right);
                t = left;
            }
            else
            {
                //rightの方が優先度高い
                Marge(ref right.left, left, right.left);
                t = right;
            }
            if (t != null) t.update();
        }

        public static void Insert(ref node root, long key, Random rand)
        {
            var item = new node(key, rand.Next());
            Insert(ref root, item);
        }

        private static void Insert(ref node t, node item)
        {
            if (t == null)
            {
                t = item;
            }
            else if (item.priority > t.priority)
            {
                //itemの方が優先度高い このノードをitemに置き換える　今のノードtはledtかrightに入る
                Split(t, item.val, out item.left, out item.right);
                t = item;
            }
            else
            {
                //こいつは優先度がヒープになることに反するので、下に潜る
                Insert(ref item.val < t.val ? ref t.left : ref t.right, item);
            }
            t.update();
        }

        public static void Erase(ref node root, long key)
        {
            EraseNode(ref root, key);
        }

        private static void EraseNode(ref node t, long key)
        {
            if (t == null) return;
            if (t.val == key)
            {
                //今いるノードを消す　このノードを子供をマージしてできた木に置き換える
                Marge(ref t, t.left, t.right);
            }
            else
            {
                //このノードは消したいノードじゃない
                EraseNode(ref key < t.val ? ref t.left : ref t.right, key);
            }
            if (t != null) t.update();
        }

        public static long GetKth(node t, int k)
        {
            if (t == null || k < 1 || k > t.cnt)
                throw new ArgumentOutOfRangeException(nameof(k));

            int leftCount = t.left != null ? t.left.cnt : 0;
            if (k <= leftCount)
            {
                return GetKth(t.left, k);
            }
            else if (k == leftCount + 1)
            {
                return t.val;
            }
            else
            {
                return GetKth(t.right, k - leftCount - 1);
            }
        }
    }

    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;
        }


    }

}