using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, q) = (c[0], c[1]);
        if (n > 3000 || q > 3000)
        {
            WriteLine(-1);
            return;
        }
        var a = NList;
        var map = NArr(q);
        var list = Create(a);
        var ans = new long[q];
        for (var i = 0; i < q; ++i)
        {
            var k = map[i][0];
            var x = map[i][1] - 1;
            var m = map[i][2];
            if (k == 1)
            {
                list = Next(list, m);
                ans[i] = Get(list, x);
            }
            else if (k == 2)
            {
                list = Next(Next(list, m), m);
                ans[i] = Get(list, x);
            }
            else if (k % 2 == 1)
            {
                list = Shift(Next(list, m), (k - 1) / 2, m);
                ans[i] = Get(list, x) % mod;
            }
            else
            {
                list = Shift(Next(Next(list, m), m), (k - 2) / 2, m);
                ans[i] = Get(list, x) % mod;
            }
        }
        WriteLine(string.Join("\n", ans));
    }
    class Range
    {
        public long Min;
        public long Max;
        public Range(long min, long max)
        {
            Min = min; Max = max;
        }
    }
    static List<Range> Create(int[] a)
    {
        var set = new HashSet<int>(a);
        var list = new List<int>(set);
        list.Sort();
        var ans = new List<Range>{ new Range(list[0], list[0] )};
        for (var i = 1; i < list.Count; ++i)
        {
            if (list[i] - list[i - 1] > 1)
            {
                ans[^1].Max = list[i - 1];
                ans.Add(new Range(list[i], list[i]));
            }
            ans[^1].Max = list[i];
        }
        return ans;
    }
    static int mod = 998_244_353;
    static List<Range> Next(List<Range> cur, int m)
    {
        var rest = (long)m;
        var ans = new List<Range>();
        for (var i = 0; i + 1 < cur.Count; ++i)
        {
            var min = cur[i].Max + 1;
            var max = Math.Min(min + rest - 1, cur[i + 1].Min - 1);
            ans.Add(new Range(min, max));
            rest -= max - min + 1;
            if (rest <= 0) break;
        }
        if (rest > 0)
        {
            var min = cur[^1].Max + 1;
            ans.Add(new Range(min, min + rest - 1));
        }
        var rem = ans[0].Min - ans[0].Min % mod;
        for (var i = 0; i < ans.Count; ++i) ans[i] = new Range(ans[i].Min - rem, ans[i].Max - rem);
        return ans;
    }
    static List<Range> Shift(List<Range> cur, int k, int m)
    {
        var loop = k / cur.Count;
        var shift = k % cur.Count;
        var ans = new List<Range>();
        var add = (long)loop * m * 2;
        for (var i = shift; i < cur.Count; ++i) ans.Add(new Range(cur[i].Min + add, cur[i].Max + add));
        for (var i = 0; i < shift; ++i) ans.Add(new Range(cur[i].Min + add + m * 2, cur[i].Max + add + m * 2));
        var rem = ans[0].Min - ans[0].Min % mod;
        for (var i = 0; i < ans.Count; ++i) ans[i] = new Range(ans[i].Min - rem, ans[i].Max - rem);
        return ans;
    }
    static long Get(List<Range> cur, int x)
    {
        var rest = (long)x;
        foreach (var ci in cur)
        {
            var count = ci.Max - ci.Min + 1;
            if (rest < count)
            {
                return ci.Min + rest;
            }
            rest -= count;
        }
        return -1;
    }
}