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.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    long mod = 998244353;
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        NTT ntt = new NTT(998244353);
        int n = ni(), k = ni();
        int[] a = new int[n];
        for(int i = 0; i< n; i++)a[i] = ni();
        long[] b = new long[n];
        for(int qq = ni(); qq>0; qq--){
            if(ni() == 1){
                long q = nl();int p = ni()-1;long d = nl();
                for(int i = 0; i< n; i++)b[i] = q-a[i];
                b[p] = q-d;
                pn((mul(ntt, b, 0, n-1)[k]+mod)%mod);
            }else{
                long q = nl();int l = ni()-1, r = ni()-1;long d = nl();
                for(int i = 0; i< l; i++)b[i] = q-a[i];
                for(int i = l; i<= r; i++)b[i] = q-a[i]-d;
                for(int i = r+1; i< n; i++)b[i] = q-a[i];
                pn((mul(ntt, b, 0, n-1)[k]+mod)%mod);
            }
        }
    }
    long[] mul(NTT ntt, long[] a, int l, int r) throws Exception{
        if(l == r)return new long[]{1, a[l]};
        int mid = (l+r)/2;
        return ntt.multiply(mul(ntt, a, l, mid), mul(ntt, a, mid+1, r));
    }
    class NTT{
        private int MAGIC = 8;
        long root, mod;
        public NTT(long m){
            mod = m;
            long[] s = pFact();
            for(root = 3; true; root++){
                boolean f = true;
                for(long x:s)if(pow(root, (mod-1)/x) == 1)f = false;
                if(f)break;
            }
        }
        long[] naiveMul(long[] a, long[] b){
            long[] c = new long[a.length+b.length-1];
            for(int i = 0; i< a.length; i++)
                for(int j = 0; j< b.length; j++)
                    c[i+j] = (c[i+j]+a[i]*b[j])%mod;
            return c;
        }
        long[] multiply(long[] a, long[] b) throws Exception{
            int l = Integer.highestOneBit(Math.max(a.length, b.length)-1)<<2;
            l = Math.max(l, 1);
            hold(mod%l == 1);
            long[] p = new long[l], q = new long[l];
            for(int i = 0; i< a.length; i++)p[i] = a[i];
            for(int i = 0; i< b.length; i++)q[i] = b[i];
            if(l <= MAGIC)return naiveMul(a, b);
            ntt(p, false);
            ntt(q, false);
            for(int i = 0; i< l; i++)p[i] = (p[i]*q[i])%mod;
            ntt(p, true);
            return p;   
        }
        void ntt(long[] p, boolean invert) throws Exception{
            int n = p.length;
            hold(bit(n) == 1);
            for(int i = 1, j = 0; i< n; i++){
                int bit = n >> 1;
                for (; j >= bit; bit >>= 1)
                    j -= bit;
                j += bit;
                if(i< j){
                    p[i] += p[j];
                    p[j] = p[i]-p[j];
                    p[i] -= p[j];
                }
            }
            hold(mod%n == 1);
            for(int len = 2; len <= n; len<<=1){
                int half = len>>1;
                hold((mod-1)%len == 0);
                long wlen = pow(root, (mod-1)/len);
                if(invert)wlen = pow(root, mod-1-(mod-1)/len);
                for(int i = 0; i< n; i+= len){
                    long w = 1;
                    for(int j = 0; j< half; j++){
                        long a = p[i+j], b = (p[i+j+half]*w)%mod;
                        p[i+j] = (a+b)%mod;
                        p[i+j+half] = (a-b+mod)%mod;
                        w = (w*wlen)%mod;
                    }
                }
            }
            long invN = pow(n, mod-2);
            if(invert)for(int i = 0; i< n; i++)p[i] = (p[i]*invN)%mod;
        }
        long pow(long a, long p){
            long o = 1;a %= mod;
            while(p>0){
                if((p&1)==1)o = (o*a)%mod;
                a = (a*a)%mod;
                p>>=1;
            }
            return o;
        }
        final long[] pFact(){
            long x = mod-1;
            long[] s = new long[15];int c = 0;
            for(long i = 2; i*i <= mod-1; i++){
                if(x%i != 0)continue;
                s[c++] = i;
                while(x%i == 0)x/= i;
            }
            if(x > 1)s[c++] = x;
            s = Arrays.copyOfRange(s, 0, c);
            return s;
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18;
    final int INF = (int)1e9+2, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("C:/users/user/desktop/inp.in");
            out = new PrintWriter("C:/users/user/desktop/out.out");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();	
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }   
}