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.*;
import java.util.*;
 
public class E implements Runnable {
	public static void main (String[] args) {new Thread(null, new E(), "_cf", 1 << 28).start();}
 
	FFT fft = new FFT();
	int[] a;
 
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");
 
		int n = fs.nextInt(), k = fs.nextInt();
		a = new int[n];
		int[] b = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = fs.nextInt();
			b[i] = a[i];
		}
		int q = fs.nextInt();
		
		for(int qq = 1; qq <= q; qq++) {
			int type = fs.nextInt();
			int val = fs.nextInt();
			
			if(type == 1) {
				int pos = fs.nextInt()-1;
				int change = fs.nextInt();
				a[pos] = change;
			}
			else {
				int L = fs.nextInt()-1, R = fs.nextInt()-1;
				int by = fs.nextInt();
				for(int i = L; i <= R; i++) a[i] = add(a[i], by);
			}
			for(int i = 0; i < n; i++) {
				a[i] = sub(val, a[i]);
			}
			long[] solve = solve(0, n - 1);
			out.println(solve[k]);
			
			for(int i = 0; i < n; i++) a[i] = b[i];
			
		}
		
		out.close();
	}
	
	long[] solve(int L, int R) {
		if(L == R) {
			return new long[] {1, a[L]};
		}
		int mid = (L + R) / 2;
		long[] left = solve(L, mid);
		long[] right = solve(mid + 1, R);
		
		return fft.multiplyPrecise(left, right);
	}
	
	int MOD = 998244353;
	
	int add(int a, int b) {
		a += b;
		if(a >= MOD) a -= MOD;
		return a;
	}
	
	int sub(int a, int b) {
		a -= b;
		if(a < 0) a += MOD;
		return a;
	}
	
	// SET maxk appropriately!!! ~log(maxn) //%
	 class FFT {
	     final int maxk = 20, maxn = (1 << maxk) + 1;
	    // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
	    //#
	     double[] wR = new double[maxn],
	            wI = new double[maxn],
	            rR = new double[maxn],
	            rI = new double[maxn],
	            aR  = new double[maxn],
	            aI  = new double[maxn]; //$
	     int n, k, lastk = -1, dp[] = new int[maxn];
 
	     void fft(boolean inv) {
	        if (lastk != k) {
	            lastk = k;  dp[0] = 0;
	            for (int i = 1, g = -1; i < n; i++) {
	                if ((i & (i - 1)) == 0) g++;
	                dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
	            }
	            wR[1] = 1;
	            wI[1] = 0;
	            for (int t = 0; t < k - 1; t++) {
	                double a = Math.PI / n * (1 << (k - 1 - t));
	                double curR = Math.cos(a), curI = Math.sin(a);
	                int p2 = (1 << t), p3 = p2 * 2;
	                for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
	                    wR[k] = wR[j];
	                    wI[k] = wI[j];
	                    wR[k + 1] = wR[j] * curR - wI[j] * curI;
	                    wI[k + 1] = wR[j] * curI + wI[j] * curR;
	                }
	            }
	        }
	        for (int i = 0; i < n; i++) {
	            int d = dp[i];
	            if (i < d) {
	                double tmp = aR[i];
	                aR[i] = aR[d];
	                aR[d] = tmp;
	                tmp = aI[i];
	                aI[i] = aI[d];
	                aI[d] = tmp;
	            }
	        }
	        if (inv) for (int i = 0; i < n; i++) aI[i] = -aI[i];
	        for (int len = 1; len < n; len <<= 1) {
	            for (int i = 0; i < n; i += len) {
	                int wit = len;
	                for (int it = 0, j = i + len; it < len; it++, i++, j++) {
	                    double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
	                    double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
	                    wit++;
	                    aR[j] = aR[i] - tmpR;
	                    aI[j] = aI[i] - tmpI;
	                    aR[i] += tmpR;
	                    aI[i] += tmpI;
	                }
	            }
	        }
	    }
 
	     long[] multiply(long[] a, long[] b) {
	        int na = a.length, nb = b.length;
	        for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {}
	        for (int i = 0; i < n; ++i) {
	            aR[i] = i < na ? a[i] : 0;
	            aI[i] = i < nb ? b[i] : 0;
	        }
	        fft(false);
	        aR[n] = aR[0];
	        aI[n] = aI[0];
	        double q = -1.0 / n / 4.0;
	        for (int i = 0; i <= n - i; ++i) {
	            double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
	            double tmpI = aR[i] * aI[i] * 2;
	            tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
	            tmpI -= aR[n - i] * aI[n - i] * -2;
	            aR[i] = -tmpI * q;
	            aI[i] = tmpR * q;
	            aR[n - i] = aR[i];
	            aI[n - i] = -aI[i];
	        }
	        fft(true);
	        long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
	        for (int i = 0; i < n; i++) ans[i] = Math.round(aR[i]) % MOD;
	        return ans;
	    }
	     void fft2(double[][] xr, double[][] xi, boolean inv) {
	        n = xr[0].length;
	        k = Integer.numberOfTrailingZeros(n);
	        for (int i = 0; i < xr.length; i++) {
	            for (int j = 0; j < n; j++) { aR[j] = xr[i][j];  aI[j] = xi[i][j]; }
	            fft(inv);
	            for (int j=0;j<n;j++){xr[i][j] = aR[j] / (inv ? n : 1);  xi[i][j] = aI[j] / (inv ? -n : 1);}
	        }
	        n = xr.length;
	        k = Integer.numberOfTrailingZeros(n);
	        for (int j = 0; j < xr[0].length; j++) {
	            for (int i = 0; i < n; i++) { aR[i] = xr[i][j];  aI[i] = xi[i][j]; }
	            fft(inv);
	            for (int i=0;i<n;i++){xr[i][j] = aR[i] / (inv ? n : 1);  xi[i][j] = aI[i] / (inv ? -n : 1);}
	        }
	    }
	     long[][] multiply2(long[][] a, long[][] b) {
	        int n1, n2;
	        for (n1 = 1; n1 < a.length + b.length - 1; n1 <<= 1) {}
	        for (n2 = 1; n2 < a[0].length + b[0].length - 1; n2 <<= 1) {}
	        double[][] ar = new double[n1][n2], ai = new double[n1][n2];
	        double[][] br = new double[n1][n2], bi = new double[n1][n2];
	        for (int i = 0; i < a.length; i++) for(int j=0;j<a[i].length;j++) ar[i][j] = a[i][j];
	        for (int i = 0; i < b.length; i++) for(int j=0;j<b[i].length;j++) br[i][j] = b[i][j];
	        fft2(ar,ai,false); fft2(br,bi,false);
	        for (int i = 0; i < n1; i++) {
	            for(int j = 0; j < n2; j++) {
	                double r1 = ar[i][j], r2 = br[i][j];
	                double i1 = ai[i][j], i2 = bi[i][j];
	                double real = r1 * r2 - i1 * i2;
	                ai[i][j] = i1 * r2+ i2*r1;
	                ar[i][j] = real;
	            }
	        }
	        fft2(ar,ai,true);  long[][] result = new long[n1=a.length+b.length-1][n2=a[0].length+b[0].length-1];
	        for (int i = 0; i < n1; i++)
	            for(int j = 0; j < n2; j++) result[i][j] = Math.round(ar[i][j]);
	        return result;
	    }
	    //#
	     long[] multiplyPrecise(long[] a, long[] b) {
	        long k = (long)(Math.sqrt(MOD));
	        long[] a1 = new long[a.length], a2 = new long[a.length];
	        long[] b1 = new long[b.length], b2 = new long[b.length];
	        for(int i=0;i<a.length;i++) {
	            a1[i] = a[i] % k;
	            a2[i] = a[i] / k;
	        }
	        for(int i=0;i<b.length;i++) {
	            b1[i] = b[i] % k;
	            b2[i] = b[i] / k;
	        }
	        long[] r11 = multiply(a1, b1), r12 = multiply(a1, b2), r21 = multiply(a2, b1), r22 = multiply(a2, b2);
	        long[] res = new long[r11.length];
	        for(int i=0;i<res.length;i++)
	            res[i] = (k*k*r22[i] + k*(r12[i] + r21[i]) + r11[i]) % MOD;
	        return res;
	    }
	    //$
	    //#
	     long[] multiplyOr(long[] eq1, long[] eq2) {
	        int n = Math.max(eq1.length, eq2.length);
	        if((n & (n-1)) != 0)
	            n = Integer.highestOneBit(n)*2;
	        eq1 = fftOr(eq1, n, false);
	        eq2 = fftOr(eq2, n, false);
	        for(int i=0;i<eq1.length;i++)
	            eq1[i] *= eq2[i];
	        eq1 = fftOr(eq1, n, true);
	        return eq1;
	    }
	    //$
	    // To use: FFT both, product, iFFT (n is next power of 2)
	     long[] fftOr(long[] arr, int n, boolean invert) {
	        long[] ans = Arrays.copyOf(arr, n);
	        for (int b = 1; b < n; b <<= 1)
	            for (int i = 0; i < n; i++) {
	                if ((i & b) != 0) continue;
	                ans[i + b] += invert ? -ans[i] : ans[i];
	            }
	        return ans;
	    }
	     long[] fftXor(long[] arr, int n, boolean invert) {
	        long[] ans = Arrays.copyOf(arr, n);
	        for (int b = 1; b < n; b <<= 1)
	            for (int i = 0; i < n; i++) {
	                if((i & b) != 0) continue;
	                long u = ans[i], v = ans[i+b];
	                ans[i] = u + v;  ans[i + b] = u - v;
	            }
	        if (invert) for (int i = 0; i < n; i++) ans[i] /= n;
	        return ans;
	    }
	}
 
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
 
		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}
 
		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}
 
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
 
		public int nextInt() {
			return (int)nextLong();
		}
 
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
 
		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}
 
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
 
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
 
		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}
 
}