using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections;
using System.Text;
using System.Text.RegularExpressions;
using static Tmpl;
using static CPDebug;
using System.Collections.Specialized;
using System.Globalization;
using System.Diagnostics;

StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));
Console.SetOut(writer);
//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));
//Console.SetIn(reader);

Solver.Solve();

Console.Out.Flush();

public static class Solver
{
    private static readonly AtCoderIO cin = new AtCoderIO();

    public static unsafe void Solve()
    {
        
        

        int N = cin.Int();
        int Q = cin.Int();
        long[] A = new long[N + 1];
        for (int i = 0; i < N; i++)
        {
            A[i + 1] = cin.Long();
        }

        ModFactorialCache cache = new(102100);

        Convolution conv = new(998244353);

        for (int i = 0; i < Q; i++)
        {
            int q = cin.Int();
            if (q == 1)
            {
                long k = cin.Long();
                int x = cin.Int();

                long[] factor = new long[N + 1];
                for (int j = 0; j <= N; j++)
                {
                    factor[j] = (cache.Combination(j + x - 1, x - 1) * ((ModInt)k).Power(j)).Raw();
                }

                A = conv.CalcConvolution(A, factor);
                Array.Resize(ref A, N + 1);
            }
            else if (q == 2)
            {
                int x = cin.Int();
                print(A[x]);
            }
        }
    }
}

// modintの階乗とその逆元を前計算して高速化.
// 前計算O(最大値). 階乗, 順列, 二項係数それぞれ定数時間.
// Depends on: ModInt
// @author Nauclhlt.
public sealed class ModFactorialCache
{
    private ModInt[] _factorial;
    private ModInt[] _inverseFactorial;

    // 階乗とその逆元を前計算する.
    // O(max)
    public ModFactorialCache(long max)
    {
        _factorial = new ModInt[max + 1];
        _inverseFactorial = new ModInt[max + 1];

        _factorial[0] = 1;
        _inverseFactorial[0] = ((ModInt)1).Inv();

        for (long p = 1; p <= max; p++)
        {
            _factorial[p] = _factorial[p - 1] * p;
            _inverseFactorial[p] = _inverseFactorial[p - 1] * ((ModInt)p).Inv();
        }
    }

    // 二項係数nCrを計算する.
    // O(1)
    public ModInt Combination(long n, long r)
    {
        return _factorial[n] * (_inverseFactorial[n - r] * _inverseFactorial[r]);
    }

    // 順列の個数nPrを計算する.
    // O(1)
    public ModInt Permutation(long n, long r)
    {
        return _factorial[n] * _inverseFactorial[n - r];
    }

    // n!を計算する.
    // O(1)
    public ModInt Factorial(long n)
    {
        return _factorial[n];
    }
}

public sealed class Convolution
{
    private readonly long _mod;
    private readonly long _primitiveRoot;
    private readonly int _maxExp;
    private readonly long _factor;
    private long[] _root;
    private long[] _inverseRoot;

    public Convolution(long mod = 998244353L)
    {
        _mod = mod;
        _primitiveRoot = FindPrimitiveRoot(mod);
        _maxExp = 0;
        long mm = mod - 1;
        while ((mm & 1) == 0)
        {
            mm >>= 1;
            _maxExp++;
        }
        _factor = mm;

        _root = new long[_maxExp + 1];
        _inverseRoot = new long[_maxExp + 1];
        CalcRoot(_root);

        for (int i = 0; i <= _maxExp; i++)
        {
            _inverseRoot[i] = Inverse(_root[i], _mod);
        }
    }

    private static long Inverse(long a, long mod)
    {
        return CalcPow(a, mod - 2, mod);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static long CalcPow(long b, long exp, long mod)
    {
        // if (exp == 0) return 1;
        // if (exp == 1) return b % mod;

        // long m = CalcPow(b, exp / 2L, mod);
        // m *= m;
		// m %= mod;
        // if (exp % 2L == 1) m *= b % mod;
        // m %= mod;

        // return m;

        b %= mod;

        long res = 1L;
        while (exp > 0)
        {
            if ((exp & 1L) == 1L)
            {
                res *= b;
                res %= mod;
            }
            b *= b;
            b %= mod;
            exp >>= 1;
        }

        return res;
    }

    private long FindPrimitiveRoot(long m)
    {
        if (m == 2) return 1;
        
        if (m == 167772161) return 3;
        if (m == 377487361) return 7;
        if (m == 469762049) return 3;
        if (m == 595591169) return 3;
        if (m == 645922817) return 3;
        if (m == 754974721) return 11;
        if (m == 880803841) return 26;
        if (m == 897581057) return 3;
        if (m == 998244353) return 3;

        List<long> divisors = new();
        long m1 = m - 1;
        for (long i = 2; i * i <= m1; i++)
        {
            if (m1 % i == 0)
            {
                while (m1 % i == 0) m1 /= i;
                divisors.Add(i);
            }
        }
        if (m1 > 1)
        {
            divisors.Add(m1);
        }

        Span<long> divSpan = CollectionsMarshal.AsSpan(divisors);

        for (long g = 2; g <= m; g++)
        {
            bool ok = true;
            for (int i = 0; i < divSpan.Length; i++)
            {
                ok &= CalcPow(g, (m - 1) / divSpan[i], m) != 1L;
            }

            if (ok)
            {
                return g;
            }
        }

        return -1;
    }

    private void CalcRoot(long[] root)
    {
        root[0] = 1L;

        root[_maxExp] = CalcPow(_primitiveRoot, _factor, _mod);
        for (int i = _maxExp - 1; i >= 1; i--)
        {
            root[i] = (root[i + 1] * root[i + 1]) % _mod;
        }
    }

    private void NTT(long[] target, int size, int exp, long[] root)
    {
        if (size == 1)
        {
            return;
        }
        else
        {
            int half = size >> 1;
            
            long[] odd = new long[half];
            long[] even = new long[half];

            for (int i = 0; i < size; i++)
            {
                if ((i & 1) == 0)
                {
                    even[i >> 1] = target[i];
                }
                else
                {
                    odd[(i - 1) >> 1] = target[i];
                }
            }

            NTT(even, half, exp - 1, root);
            NTT(odd, half, exp - 1, root);

            long r = root[exp];

            long f = 1L;

            for (int i = 0; i < size; i++)
            {
                target[i] = (even[i % half] + (f * odd[i % half]) % _mod) % _mod;
                f *= r;
                f %= _mod;
            }
        }
    }

    private void ButterflyNTT(Span<long> target, int exp, long[] root)
    {
        if (target.Length == 1) return;

        int n = target.Length;
        int k = exp;
        int r = 1 << (k - 1);
        for (int m = k; m > 0; m--) 
        {
            for (int l = 0; l < n; l += (r << 1)) 
            {
                long wi = 1;
                for (int i = 0; i < r; i++) 
                {
                    long temp = (target[l + i] + target[l + i + r]) % _mod;
                    target[l + i + r] = (target[l + i] - target[l + i + r]) * wi % _mod;
                    target[l + i] = temp;
                    wi = wi * root[m] % _mod;
                }
            }
            r >>= 1;
        }
    }

    private void ButterflyINTT(Span<long> target, int exp, long[] root)
    {
        if (target.Length == 1)
            return;
        int n = target.Length;
        int k = exp;
        int r = 1;
        for (int m = 1; m < k + 1; m++)
        {
            for (int l = 0; l < n; l += (r << 1)) 
            {
                long wi = 1;
                for (int i = 0; i < r; i++) 
                {
                    long temp = (target[l + i] + target[l + i + r] * wi) % _mod;
                    target[l + i + r] = (target[l + i] - target[l + i + r] * wi) % _mod;
                    target[l + i] = temp;
                    wi = wi * root[m] % _mod;
                }
            }
            r <<= 1;
        }

        long ni = Inverse(n, _mod);
        for (int i = 0; i < n; i++) {
            target[i] = ((target[i] * ni % _mod) + _mod) % _mod;
        }
    }

    public long[] CalcConvolution(long[] a, long[] b)
    {
        int dsize = a.Length + b.Length;

        int exp = 0;
        while ((1 << exp) < dsize)
        {
            exp++;
        }
        int n = 1 << exp;

        if (exp > _maxExp)
        {
            throw new InvalidOperationException("Data too large.");
        }

        long[] buffer = new long[n];
        long[] c = new long[n];

        Array.Copy(a, 0, c, 0, a.Length);
        Array.Copy(b, 0, buffer, 0, b.Length);

        ButterflyNTT(c, exp, _root);
        ButterflyNTT(buffer, exp, _root);

        for (int i = 0; i < n; i++)
        {
            c[i] *= buffer[i];
            c[i] %= _mod;
        }

        ButterflyINTT(c, exp, _inverseRoot);

        return c;
    }

    private static long SafeMod(long x, long m)
    {
        x %= m;
        if (x < 0) x += m;
        return x;
    }

    private static long ExtEuclid(long a, long b, ref long p, ref long q)
    {
        if (b == 0)
        {
            p = 1;
            q = 0;
            return a;
        }
        long d = ExtEuclid(b, a % b, ref q, ref p);
        q -= a / b * p;
        return d;
    }

    private static (long rem, long mod) CRT(long x1, long m1, long x2, long m2)
    {
        long p = 0, q = 0;
        long d = ExtEuclid(m1, m2, ref p, ref q);
        if ((x2 - x1) % d != 0)
            return (0, -1);

        long m = m1 * (m2 / d);
        long temp = (x2 - x1) / d * p % (m2 / d);
        long r = SafeMod(x1 + m1 * temp, m);
        return (r, m);
    }

    private static (long rem, long mod) CRT(List<long> x, List<long> mod)
    {
        long r = 0, m = 1;
        for (int i = 0; i < x.Count; i++)
        {
            long p = 0, q = 0;
            long d = ExtEuclid(m, mod[i], ref p, ref q);
            if ((x[i] - r) % d != 0)
                return (0, -1);
            long temp = (x[i] - r) / d * p % (mod[i] / d);
            r += m * temp;
            m *= mod[i] / d;
        }

        return (SafeMod(r, m), m);
    }
}

public struct Vector<T> where T : struct, INumber<T>
{
    private T[] _data;
    private int _size;

    public T this[int index]
    {
        get => _data[index];
        set => _data[index] = value;
    }

    public int Size => _size;
    public T[] Data => _data;

    public Vector(int size)
    {
        _data = new T[size];
        _size = size;
    }
}

public struct Matrix<T> where T : struct, INumber<T>
{
    private T[,] _data;
    private int _size;

    public T this[int r, int c]
    {
        get
        {
            return _data[r, c];
        }
        set
        {
            _data[r, c] = value;
        }
    }

    public T[,] Data => _data;
    public int Size => _size;

    public Matrix(int size)
    {
        _size = size;
        _data = new T[size, size];
    }

    public static Matrix<T> operator +(Matrix<T> left, Matrix<T> right)
    {
        if (left.Size != right.Size)
        {
            throw new InvalidOperationException();
        }
        Matrix<T> dest = new(left.Size);
        for (int r = 0; r < left.Size; r++)
        {
            for (int c = 0; c < left.Size; c++)
            {
                dest[r, c] = left[r, c] + right[r, c];
            }
        }

        return dest;
    }

    public static Matrix<T> operator -(Matrix<T> left, Matrix<T> right)
    {
        if (left.Size != right.Size)
        {
            throw new InvalidOperationException();
        }
        Matrix<T> dest = new(left.Size);
        for (int r = 0; r < left.Size; r++)
        {
            for (int c = 0; c < left.Size; c++)
            {
                dest[r, c] = left[r, c] - right[r, c];
            }
        }

        return dest;
    }

    public static Matrix<T> operator *(Matrix<T> left, Matrix<T> right)
    {
        if (left.Size != right.Size)
        {
            throw new InvalidOperationException();
        }

        Matrix<T> dest = new(left.Size);

        for (int r = 0; r < dest.Size; r++)
        {
            for (int c = 0; c < dest.Size; c++)
            {
                for (int i = 0; i < dest.Size; i++)
                {
                    dest[r, c] += right[i, c] * left[r, i];
                }
            }
        }

        return dest;
    }

    public override string ToString()
    {
        StringBuilder sb = new();
        for (int r = 0; r < _size; r++)
        {
            sb.Append('|');
            for (int c = 0; c < _size; c++)
            {
                sb.Append(_data[r, c]);
                if (c != _size - 1)
                {
                    sb.Append(',');
                    sb.Append('\t');
                }
                
            }
            sb.Append('|');
            sb.Append(Environment.NewLine);
        }

        return sb.ToString();
    }
}

static class Constants
{
    public const long Mod = 998244353L;
    //public const long Mod = 10007L;
    //public const long Mod = 1000000007L;
}

public readonly struct Point
{
    public readonly int X;
    public readonly int Y;

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public override int GetHashCode() => (X, Y).GetHashCode();

    public override string ToString()
    {
        return $"({X}, {Y})";
    }
}

public sealed class ReverseComparer<T> : IComparer<T>
{
    public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);

    public static ReverseComparer<T> Reverse(IComparer<T> comparer)
    {
        return new ReverseComparer<T>(comparer);
    }

    private readonly IComparer<T> comparer = Default;

    private ReverseComparer(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return comparer.Compare(y, x);
    }
}

public sealed class AtCoderIO
{
    Queue<string> _readQueue = new Queue<string>();

    private void LoadQueue()
    {
        if (_readQueue.Count > 0) return;
        string line = Console.ReadLine();
        string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
    }

    private void Guard()
    {
        if (_readQueue.Count == 0)
        {
            throw new Exception("NO DATA TO READ");
        }
    }

    public int Int()
    {
        LoadQueue();
        Guard();
        return int.Parse(_readQueue.Dequeue());
    }

    public long Long()
    {
        LoadQueue();
        Guard();
        return long.Parse(_readQueue.Dequeue());
    }

    public string String()
    {
        LoadQueue();
        Guard();
        return _readQueue.Dequeue();
    }

    public short Short()
    {
        LoadQueue();
        Guard();
        return short.Parse(_readQueue.Dequeue());
    }

    public byte Byte()
    {
        LoadQueue();
        Guard();
        return byte.Parse(_readQueue.Dequeue());
    }

    public char Char()
    {
        LoadQueue();
        Guard();
        return char.Parse(_readQueue.Dequeue());
    }

    public double Double()
    {
        LoadQueue();
        Guard();
        return double.Parse(_readQueue.Dequeue());
    }

    public float Float()
    {
        LoadQueue();
        Guard();
        return float.Parse(_readQueue.Dequeue());
    }

    public ModInt ModInt()
    {
        return new ModInt(Long());
    }

    public T Read<T>()
    {
        Type type = typeof(T);
        if (type == typeof(int)) return (T)(object)Int();
        else if (type == typeof(long)) return (T)(object)Long();
        else if (type == typeof(float)) return (T)(object)Float();
        else if (type == typeof(double)) return (T)(object)Double();
        else if (type == typeof(short)) return (T)(object)Short();
        else if (type == typeof(byte)) return (T)(object)Byte();
        else if (type == typeof(char)) return (T)(object)Char();
        else if (type == typeof(string)) return (T)(object)String();
        else if (type == typeof(ModInt)) return (T)(object)ModInt();
        else return default(T);
    }

    public int[] IntArray(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int();
        }

        return arr;
    }

    public int[] ZeroIndexedPermutation(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int() - 1;
        }

        return arr;
    }

    public long[] LongArray(int n)
    {
        if (n == 0) return Array.Empty<long>();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Long();
        }

        return arr;
    }

    public double[] DoubleArray(int n)
    {
        if (n == 0) return Array.Empty<double>();

        double[] arr = new double[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Double();
        }

        return arr;
    }

    public ModInt[] ModIntArray(int n)
    {
        if (n == 0) return Array.Empty<ModInt>();

        ModInt[] arr = new ModInt[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = (ModInt)Long();
        }

        return arr;
    }

    public T[] ReadArray<T>(int n)
    {
        if (n == 0) return Array.Empty<T>();

        T[] arr = new T[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Read<T>();
        }

        return arr;
    }
}

public static class CPDebug
{
    public static void check<T>(T value, [CallerArgumentExpression(nameof(value))] string name = "value")
    {
#if DEBUG
        Console.WriteLine($"[DEBUG] {name}={value.ToString()}");
#endif
    }

    public static void check<T>(IEnumerable<T> value, [CallerArgumentExpression(nameof(value))] string name = "value")
    {
#if DEBUG
        Console.WriteLine($"[DEBUG] {name}=({string.Join(' ', value)})");
#endif
    }
}

public static class Tmpl
{
    public static int combination(int n, int r)
    {
        int c = 1;
        for (int i = 1; i <= r; i++)
        {
            c = c * (n - i + 1) / i;
        }
        return c;
    }

    public static long combination(long n, long r)
    {
        long c = 1;
        for (long i = 1; i <= r; i++)
        {
            c = c * (n - i + 1) / i;
        }
        return c;
    }

    public static long pow(long b, long exp)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b;

        long m = pow(b, exp / 2L);
        m *= m;
        if (exp % 2L == 1) m *= b;

        return m;
    }

    public static long modpow(long b, long exp, long mod)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b % mod;

        long m = modpow(b, exp / 2L, mod);
        m *= m;
		m %= mod;
        if (exp % 2L == 1) m *= b % mod;
        m %= mod;

        return m;
    }

	static long modinv( long a, long mod )
	{
		long b = mod, u = 1, v = 0;
		while ( b > 0 )
		{
			long t = a / b;
			a -= t * b; swap( ref a, ref b );
			u -= t * v; swap( ref u, ref v );
		}
		u %= mod;
		if (u < 0) u += mod;
		return u;
	}

    public static long calcLcm(long a, long b)
    {
        return a * b / calcGcd(a, b);
    }

    public static long calcGcd(long a, long b)
    {
        if (a % b == 0) return b;
        return calcGcd(b, a % b);
    }

    // ax ≡ b (mod m)なる最小のxを求める
    public static bool solveModLinear(long a, long b, long m, out long minSolution)
    {
        long gcd = calcGcd(calcGcd(a, b), m);
        a /= gcd;
        b /= gcd;
        m /= gcd;
        if (calcGcd(a, m) == 1)
        {
            long inv = modinv(a, m);
            minSolution = (b * inv) % m;
            return true;
        }
        minSolution = 0;
        return false;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YesNo(bool t)
    {
        Console.WriteLine(t ? "Yes" : "No");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YESNO(bool t)
    {
        Console.WriteLine(t ? "YES" : "NO");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void yesno(bool t)
    {
        Console.WriteLine(t ? "yes" : "no");
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool checkBit(int bit, int n)
    {
        return ((1 << n) & bit) != 0;
    }

    public static bool nextCombination(int n, int r, int[] array)
    {
        int i = array.Length - 1;
        while (i >= 0 && array[i] == i + n - r)
        {
            i--;
        }

        if (i < 0) return false;

        array[i]++;
        for (int j = i + 1; j < r; j++)
        {
            array[j] = array[j - 1] + 1;
        }

        return true;
    }

    public static bool nextPermutation<T>(T[] array, int start, int length) where T : IComparable<T>
    {
        int end = start + length - 1;

        if (end <= start) return false;

        int last = end;
        while (true)
        {
            int pos = last--;
            
            if (array[last].CompareTo(array[pos]) < 0)
            {
                int i;
                for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
                T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
                Array.Reverse(array, pos, end - pos + 1);
                return true;
            }
            if (last == start)
            {
                Array.Reverse(array, start, end - start);
                return false;
            }
        }

        throw new Exception("NextPermutation: Fatal error");
    }

    public static unsafe Dictionary<char, int> cntCharOcc(string s)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();
        fixed (char* ptr = s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                if (dict.ContainsKey(ptr[i]))
                {
                    dict[ptr[i]] += 1;
                }
                else
                {
                    dict[ptr[i]] = 1;
                }
            }
        }

        return dict;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void chmax<T> (ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value > target)
        {
            target = value;
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void chmin<T>(ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value < target)
        {
            target = value;
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void arrMod<T>(T[] array, T b) where T : IModulusOperators<T, T, T>
    {
        for (int i = 0; i < array.Length; i++)
        {
            array[i] %= b;
        }
    }

    public static ReadOnlySpan<T> spanOf<T>(List<T> list)
    {
        return CollectionsMarshal.AsSpan(list);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(T[] array, int i, int j) where T : struct
    {
        (array[i], array[j]) = (array[j], array[i]);
    }

    public static void shuffle<T>(T[] array) where T : struct
    {
        Random random = new Random();
        for (int i = array.Length - 1; i > 0; i--)
        {
            int index = random.Next(0, i + 1);
            swap(array, index, i);
        }
    }

    public static int lowerBound<T>(T[] array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }

        if (low == array.Length - 1 && array[low] < value)
        {
            return array.Length;
        }
        return low;
    }

    public static int lowerBound<T>(List<T> array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }

        if (low == array.Count - 1 && array[low] < value)
        {
            return array.Count;
        }
        return low;
    }

    public static int upperBound<T>(T[] array, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        var l = 0;
        var r = array.Length - 1;
        while (l <= r)
        {
            var mid = l + (r - l) / 2;
            if (array[mid] <= value) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(ref T a, ref T b) where T : struct
    {
        T temp = a;
        a = b;
        b = temp;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool dbleq(double a, double b)
    {
        return Math.Abs(a - b) < double.Epsilon;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int dblAsInt(double d)
    {
        return (int)Math.Round(d, 0);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static long dblAsLong(double d)
    {
        return (long)Math.Round(d, 0);
    }

    public static int[] compressCoords<T>(T[] a) where T : struct, IComparisonOperators<T, T, bool>
    {
        T[] b = a.OrderBy(x => x).Distinct().ToArray();
        int[] result = new int[a.Length];

        for (int i = 0; i < a.Length; i++)
        {
            result[i] = lowerBound(b, 0, b.Length - 1, a[i]);
        }

        return result;
    }

    public static List<RunLengthElement<T>> compressRunLength<T>(T[] array) where T : struct, IEquatable<T>
    {
        List<RunLengthElement<T>> list = new List<RunLengthElement<T>>();

        int count = 1;
        int start = 0;
        T prev = array[0];

        for (int i = 1; i < array.Length; i++)
        {
            if (prev.Equals(array[i]))
            {
                count++;
            }
            else
            {
                list.Add(new RunLengthElement<T>(start, count, prev));
                start = i;
                count = 1;
            }

            prev = array[i];
        }

        list.Add(new RunLengthElement<T>(start, count, prev));

        return list;
    }

    public static char[] alphabetsLower()
    {
        return new[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    }

    public static char[] alphebetsUpper()
    {
        return new[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        Console.WriteLine(string.Join(delimiter, array));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        print(array);
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(string msg)
    {
        Console.WriteLine(msg);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(string msg)
    {
        Console.WriteLine(msg);
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(int val)
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(long val)
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(ModInt val)
    {
        print(val.ToString());
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(int val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(long val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(ModInt val)
    {
        fprint(val.ToString());
        Console.Out.Flush();
    }

    public static void print<T>(T[,] grid)
    {
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                Console.Write(grid[y, x] + "\t");
            }
            Console.WriteLine();
        }
    }

    public static void print01(bool t)
    {
        Console.WriteLine(t ? "1" : "0");
    }

    public static TSrc lowerBoundKth<TSrc, TCnt>(TSrc min, TSrc max, Func<TSrc, TCnt> f, TCnt bound)
        where TSrc: struct, INumber<TSrc> where TCnt: struct, INumber<TCnt>
    {
        TSrc left = min;
        TSrc right = max;
        TSrc two = TSrc.CreateChecked(2);
        TSrc one = TSrc.CreateChecked(1);
        while (right > left)
        {
            TSrc mid = left + (right - left) / two;
            TCnt c = f(mid);
            if (c < bound)
            {
                left = mid + one;
            }
            else
            {
                right = mid;
            }
        }

        return left;
    }

    public static bool isSquareNumber(long n)
    {
        long q = (long)Math.Floor(Math.Sqrt(n));
        return q * q == n;
    }
}

public readonly struct RunLengthElement<T> where T : struct
{
    public readonly int Count;
    public readonly int StartIndex;
    public readonly T Value;

    public RunLengthElement(int startIndex, int count, T value)
    {
        this.StartIndex = startIndex;
        this.Count = count;
        this.Value = value;
    }
}

public readonly struct Edge<T> : IEquatable<Edge<T>>, IComparable<Edge<T>> where T : struct, INumber<T>
{
    public readonly int To;
    public readonly int From;
    public readonly T Weight;

    public Edge(int to, T weight)
    {
        this.To = to;
        this.Weight = weight;
    }

    public Edge(int from, int to, T weight)
    {
        this.To = to;
        this.From = from;
        this.Weight = weight;
    }

    public override bool Equals(object obj)
    {
        if (obj is Edge<T> edge)
        {
            return this.Equals(edge);
        }
        else
        {
            return false;
        }
    }

    public int CompareTo(Edge<T> other)
    {
        return Weight.CompareTo(other.Weight);
    }

    public bool Equals(Edge<T> edge)
    {
        return To == edge.To && From == edge.From && Weight == edge.Weight;
    }

    public override int GetHashCode()
    {
        return (To, From, Weight).GetHashCode();
    }

    public static bool operator ==(Edge<T> left, Edge<T> right)
    {
        return left.Equals(right);
    }

    public static bool operator !=(Edge<T> left, Edge<T> right)
    {
        return !left.Equals(right);
    }
}

public readonly struct ModInt : IEquatable<ModInt>
{
    private readonly long Value;

    public static ModInt One => (ModInt)1L;

    public static ModInt Zero => (ModInt)0L;

    public ModInt(long value)
    {
        Value = SafeMod(value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static long SafeMod(long a)
    {
        a %= Constants.Mod;
        if (a < 0) a += Constants.Mod;
        return a;
    }

    public ModInt Power(long exp)
    {
        if (exp <= -1) return this;
        if (exp == 0) return 1;
        if (exp == 1) return this;

        ModInt m = Power(exp / 2);
        m *= m;
        if (exp % 2 == 1) m *= this;

        return m;
    }

    public ModInt Inv()
    {
        return this.Power(Constants.Mod - 2L);
    }

    public static ModInt operator +(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value + right.Value));
    }

    public static ModInt operator -(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value - right.Value));
    }

    public static ModInt operator *(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value * right.Value));
    }

    public static ModInt operator /(ModInt left, ModInt right)
    {
        if (right.Value == 0L)
        {
            return Zero;
        }

        ModInt inv = right.Inv();
        return SafeMod(left * inv);
    }

    public static ModInt operator %(ModInt left, ModInt right)
    {
        if (right.Value == 0L)
        {
            return Zero;
        }

        return new ModInt(SafeMod(left.Value % right.Value));
    }

    public static bool operator ==(ModInt left, ModInt right)
    {
        return left.Value == right.Value;
    }

    public static bool operator != (ModInt left, ModInt right)
    {
        return !(left == right);
    }

    public bool Equals(ModInt other)
    {
        return Value == other.Value;
    }

    public override bool Equals(object other)
    {
        if (other is ModInt m)
        {
            return this == m;
        }
        else return false;
    }

    public override int GetHashCode()
    {
        return Value.GetHashCode();
    }

    public static implicit operator ModInt(long v)
    {
        return new ModInt(v);
    }

    public static implicit operator ModInt(int v)
    {
        return new ModInt(v);
    }

    public static implicit operator long(ModInt m)
    {
        return m.Value;
    }

    public static implicit operator int(ModInt m)
    {
        return (int)m.Value;
    }

    public long Raw() => Value;

    public override string ToString()
    {
        return Value.ToString();
    }
}