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
#include <bits/stdc++.h>
using namespace std;
const int G = 3;
const int MOD = 998244353;
const int N = (1 << 15) + 5;
int rev[N], w[N], inv_n;
int bigMod(int a, int e, int mod) {
  if (e == -1) e = mod - 2;
  int ret = 1;
  while (e) {
    if (e & 1) ret = (long long)ret * a % mod;
    a = (long long)a * a % mod;
    e >>= 1;
  }
  return ret;
}
void prepare(int &n) {
  int sz = abs(31 - __builtin_clz(n));
  int r = bigMod(G, (MOD - 1) / n, MOD);
  inv_n = bigMod(n, MOD - 2, MOD), w[0] = w[n] = 1;
  for (int i = 1; i < n; ++i) w[i] = (long long)w[i - 1] * r % MOD;
  for (int i = 1; i < n; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
}
void ntt(int *a, int n, int dir) {
  for (int i = 1; i < n - 1; ++i) {
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  }
  for (int m = 2; m <= n; m <<= 1) {
    for (int i = 0; i < n; i += m) {
      for (int j = 0; j < (m >> 1); ++j) {
        int &u = a[i + j], &v = a[i + j + (m >> 1)];
        int t = (long long)v * w[dir ? n - n / m * j : n / m * j] % MOD;
        v = u - t < 0 ? u - t + MOD : u - t;
        u = u + t >= MOD ? u + t - MOD : u + t;
      }
    }
  }
  if (dir)
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv_n % MOD;
}
int f_a[N], f_b[N];
vector<long long> multiply(vector<long long> a, vector<long long> b) {
  int sz = 1, n = a.size(), m = b.size();
  while (sz < n + m - 1) sz <<= 1;
  prepare(sz);
  for (int i = 0; i < sz; ++i) f_a[i] = i < n ? a[i] : 0;
  for (int i = 0; i < sz; ++i) f_b[i] = i < m ? b[i] : 0;
  ntt(f_a, sz, 0);
  ntt(f_b, sz, 0);
  for (int i = 0; i < sz; ++i) f_a[i] = (long long)f_a[i] * f_b[i] % MOD;
  ntt(f_a, sz, 1);
  return vector<long long>(f_a, f_a + n + m - 1);
}
int n, k, q;
long long a[N], b[N];
vector<long long> get(int lo, int hi) {
  if (lo == hi) return {b[lo], 1};
  int mid = lo + hi >> 1;
  vector<long long> one = get(lo, mid);
  vector<long long> two = get(mid + 1, hi);
  return multiply(one, two);
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
  cin >> q;
  while (q--) {
    long long cmd, x, l, r, p;
    scanf("%lld %lld %lld %lld", &cmd, &x, &l, &r);
    if (cmd == 1) {
      for (int i = 1; i <= n; ++i) {
        b[i] = a[i];
        if (i == l) b[i] = r;
      }
    } else {
      scanf("%lld", &p);
      for (int i = 1; i <= n; ++i) {
        b[i] = a[i];
        if (l <= i and i <= r) b[i] += p;
      }
    }
    for (int i = 1; i <= n; ++i) {
      b[i] = x - b[i], b[i] %= MOD;
      if (b[i] < 0) b[i] += MOD;
    }
    vector<long long> yo = get(1, n);
    printf("%lld\n", yo[n - k]);
  }
  return 0;
}
