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 inf = 1e9;
const long long inf64 = 1e18;
const int mod = 998244353;
const int root = 31 * 31 * 31 * 31;
const int LOG = 21;
const int N = 1e5 + 5;
vector<int> G[LOG + 1];
vector<int> rev[LOG + 1];
inline void _add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}
inline int _sum(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
inline int _sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
inline int _mul(int a, int b) { return (1ll * a * b) % mod; }
inline int _binpow(int x, int p) {
  int res = 1;
  int tmp = x;
  while (p > 0) {
    if (p & 1) {
      res = _mul(res, tmp);
    }
    tmp = _mul(tmp, tmp);
    p >>= 1;
  }
  return res;
}
inline int _rev(int x) { return _binpow(x, mod - 2); }
void precalc() {
  for (int start = root, lvl = LOG; lvl >= 0;
       lvl--, start = _mul(start, start)) {
    int tot = 1 << lvl;
    G[lvl].resize(tot);
    for (int cur = 1, i = 0; i < tot; i++, cur = _mul(cur, start)) {
      G[lvl][i] = cur;
    }
  }
  for (int lvl = 1; lvl <= LOG; lvl++) {
    int tot = 1 << lvl;
    rev[lvl].resize(tot);
    for (int i = 1; i < tot; i++) {
      rev[lvl][i] = ((i & 1) << (lvl - 1)) | (rev[lvl][i >> 1] >> 1);
    }
  }
}
void fft(vector<int> &a, int sz, bool invert) {
  int n = 1 << sz;
  for (int j, i = 0; i < n; i++) {
    if ((j = rev[sz][i]) < i) {
      swap(a[i], a[j]);
    }
  }
  for (int f1, f2, lvl = 0, len = 1; len < n; len <<= 1, lvl++) {
    for (int i = 0; i < n; i += (len << 1)) {
      for (int j = 0; j < len; j++) {
        f1 = a[i + j];
        f2 = _mul(a[i + j + len], G[lvl + 1][j]);
        a[i + j] = _sum(f1, f2);
        a[i + j + len] = _sub(f1, f2);
      }
    }
  }
  if (invert) {
    reverse(a.begin() + 1, a.end());
    int rn = _rev(n);
    for (int i = 0; i < n; i++) {
      a[i] = _mul(a[i], rn);
    }
  }
}
vector<int> multiply(const vector<int> &a, const vector<int> &b) {
  vector<int> fa(a.begin(), a.end());
  vector<int> fb(b.begin(), b.end());
  int n = (int)a.size();
  int m = (int)b.size();
  int maxnm = max(n, m), sz = 0;
  while ((1 << sz) < maxnm) sz++;
  sz++;
  fa.resize(1 << sz);
  fb.resize(1 << sz);
  fft(fa, sz, false);
  fft(fb, sz, false);
  int SZ = 1 << sz;
  for (int i = 0; i < SZ; i++) {
    fa[i] = _mul(fa[i], fb[i]);
  }
  fft(fa, sz, true);
  while ((int)fa.size() > 1 && !fa.back()) fa.pop_back();
  return fa;
}
vector<int> solve(const vector<int> &b, int l, int r) {
  if (l == r) {
    return {1, b[l]};
  }
  int m = (l + r) / 2;
  vector<int> le = solve(b, l, m);
  vector<int> ri = solve(b, m + 1, r);
  return multiply(le, ri);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b;
  int lg = 0;
  while ((1 << lg) <= n) lg++;
  lg++;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int Q;
  cin >> Q;
  for (int iter = 0; iter < Q; iter++) {
    int type, q;
    cin >> type;
    b = a;
    if (type == 1) {
      int i, d;
      cin >> q >> i >> d;
      i--;
      b[i] = d;
    } else {
      int l, r, d;
      cin >> q >> l >> r >> d;
      l--, r--;
      for (int i = l; i <= r; i++) {
        _add(b[i], d);
      }
    }
    for (int i = 0; i < n; i++) {
      b[i] = _sub(q, b[i]);
    }
    vector<int> f = solve(b, 0, n - 1);
    cout << f[k] << "\n";
  }
  return 0;
}
