Problem: While roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array A = {a_1,a_2,...,a_N } of length N, and a number K.

Define array B as B(q, A) =  { q-a_1, q-a_2, ..., q-a_N }. Define function F as F(B,K) being sum of products of all K-tuples of elements in array B. For example, if the array B is [2,3,4,5], and with K=3, sum of products of all 3-tuples is $$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$$

He was then given a number Q, number of queries of two types: 

  * Type 1: Given q, i, and d calculate F(B(q, A), K) where we make change to initial array as A[i] = d. 
  * Type 2: Given q, L, R, and d calculate F(B(q, A), K) where we make change to initial array as A[i] = A[i] + d for all i in range [L, R] inclusive. 



All changes are temporarily made to initial array, and don't propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!

Input

In the first two lines, numbers N (1 ≤ N ≤ 2*10^4) and K (1 ≤ K ≤ N), the length of initial array A, and tuple size, followed by a_1,a_2,a_3,…,a_N (0 ≤ a_i ≤ 10^9) , elements of array A, in the next line. Then follows number Q (Q ≤ 10), number of queries. In the next Q lines come queries of the form: 

  * 1 q i d, for type 1, 
  * 2 q L R d, for type 2, 



as explained above (0 ≤ q, d ≤ 10^9, 1 ≤ i,L,R ≤ N)

Output

Print Q lines, the answers to queries, modulo 998244353.

Example

Input


5
2
1 2 3 4 5
3
1 6 1 1
1 6 5 2
2 6 2 3 1


Output


85
127
63

Note

In the first query array A = [1, 2, 3, 4, 5], B = [5, 4, 3, 2, 1], sum of products of 2-tuples = 85.

In second query array A = [1, 2, 3, 4, 2], B = [5, 4, 3, 2, 4], sum of products of 2-tuples = 127

In third query array A = [1, 3, 4, 4, 5], B = [5, 3, 2, 2, 1], sum of products of 2-tuples = 63

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author beginner1010
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        final int MOD = 998244353;

        int pow(int a, int b) {
            if (b == 0)
                return 1;
            if ((b & 1) == 1) {
                return mul(a, pow(a, b - 1));
            } else {
                int aux = pow(a, b >> 1);
                return mul(aux, aux);
            }
        }

        int mul(int a, int b) {
            return (int) ((1L * a * b) % MOD);
        }

        int add(int a, int b) {
            return ((int) (1L * a + b) % MOD);
        }

        int sub(int a, int b) {
            long ans = a;
            ans -= b;
            ans %= MOD;
            if (ans < 0) ans += MOD;
            return (int) ans;
        }

        int inv(int a) {
            return pow(a, MOD - 2);
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sub(in.nextInt(), 0);
            }

            int query = in.nextInt();
            FFT fft = new FFT();
            for (int i = 0; i < query; i++) {
                int type = in.nextInt();
                int[] b = new int[n];
                if (type == 1) {
                    int q = in.nextInt();
                    int id = in.nextInt() - 1;
                    int d = in.nextInt();
                    for (int j = 0; j < n; j++) {
                        b[j] = id == j ? sub(q, d) : sub(q, a[j]);
                    }
                } else {
                    int q = in.nextInt();
                    int l = in.nextInt() - 1;
                    int r = in.nextInt() - 1;
                    int d = in.nextInt();
                    for (int j = 0; j < n; j++) {
                        b[j] = l <= j && j <= r ? sub(q, add(a[j], d)) : sub(q, a[j]);
                    }
                }
                int[] ans = fft.get(0, n - 1, b);
                out.println(k >= ans.length ? 0 : ans[k]);
            }
        }

        class FFT {
            final int maxN = 4 * 4 * 10000;
            final int G = 3;
            int[] rev;

            FFT() {
                rev = new int[maxN];
            }

            void FFT(int[] a, boolean inverse) {
                int n = a.length;
                for (int i = 0; i < a.length; i++) {
                    if (i < rev[i]) {
                        int temp = a[i];
                        a[i] = a[rev[i]];
                        a[rev[i]] = temp;
                    }
                }
                for (int i = 1; i < n; i *= 2) {
                    int wn = pow(G, ((MOD - 1) / i) >> 1);
                    if (inverse == true) wn = inv(wn);
                    for (int j = 0; j < n; j += i * 2) {
                        int w = 1;
                        for (int k = j; k < j + i; k++) {
                            int x = a[k], y = mul(w, a[k + i]);
                            a[k] = add(x, y);
                            a[k + i] = sub(x, y);
                            w = mul(w, wn);
                        }
                    }
                }
                if (inverse == true) {
                    int nInv = inv(n);
                    for (int i = 0; i < n; i++) {
                        a[i] = mul(a[i], nInv);
                    }
                }
            }

            int[] multiply(int[] a, int[] b) {
                int n = Math.max(a.length, b.length);
                int n2 = 1;
                int log = 0, m = n * 2;
                while (n2 < m) {
                    n2 *= 2;
                    log++;
                }
                for (int i = 0; i < n2; i++) {
                    rev[i] = (rev[i >> 1] >> 1) ^ ((i & 1) << (log - 1));
                }
                a = Arrays.copyOf(a, n2);
                b = Arrays.copyOf(b, n2);
                FFT(a, false);
                FFT(b, false);
                for (int i = 0; i < a.length; i++) a[i] = mul(a[i], b[i]);
                FFT(a, true);
                return a;
            }

            int[] get(int l, int r, int[] a) {
                if (l == r) {
                    int[] res = new int[2];
                    res[0] = 1;
                    res[1] = a[l];
                    return res;
                }
                int mid = (l + r) >> 1;
                int[] f1 = get(l, mid, a);
                int[] f2 = get(mid + 1, r, a);
                int[] g = multiply(f1, f2);
                int size = g.length;
                while (size > 0 && g[size - 1] == 0) {
                    size--;
                }
                g = Arrays.copyOf(g, size);
                return g;
            }

        }

    }

    static class InputReader {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputStream stream;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isWhitespace(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isWhitespace(c));
            return res * sgn;
        }

    }
}