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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MN = 20020;
const int MQ = 12;
const int LOG = 17;
const int MF = (1 << 18) + 10;
const long long M = 998244353;
long long w[MN];
long long mul(long long a, long long b) { return (a * b) % M; }
long long bp(long long b, long long p) {
  long long ac = 1;
  while (p) {
    if (p & 1) {
      ac = mul(ac, b);
    }
    b = mul(b, b);
    p >>= 1;
  }
  return ac;
}
long long inv(long long n) { return bp(n, M - 2); }
class NTT {
 private:
  static const long long G = 3;
  int n, len, log;
  long long invn;
  vector<long long> w;
  vector<long long> rev;
  vector<long long> tp[2];

 public:
  NTT() {}
  NTT(int _n) {
    len = 1;
    log = 0;
    n = _n;
    while (len <= n) {
      len <<= 1;
      log++;
    }
    invn = inv(len);
    w.assign(len + 10, 0);
    rev.assign(len + 10, 0);
    for (long long i = 0; i < len; i++) {
      w[i] = bp(G, i * (M - 1) / len);
    }
    rev[0] = 0;
    for (int i = 1; i < len; i++) {
      int k = 0;
      while (((i >> k) & 1) == 0) {
        k++;
      }
      rev[i] = rev[i ^ (1 << k)] ^ (1 << (log - 1 - k));
    }
    tp[0].assign(len + 10, 0);
    tp[1].assign(len + 10, 0);
  }
  void ntt(vector<long long>& v) {
    for (int i = 0; i < len; i++) {
      tp[0][rev[i]] = v[i];
    }
    int t = 0, nt = 1;
    for (int id = 0; id < log; id++) {
      int cv = 1 << id;
      for (int k = 0; k < len; k += 1 << (id + 1)) {
        for (int i = 0; i < cv; i++) {
          long long ad = mul(tp[t][k + cv + i], w[i << (log - 1 - id)]);
          tp[nt][k + i] = tp[t][k + i] + ad;
          tp[nt][k + cv + i] = tp[t][k + i] + M - ad;
          if (tp[nt][k + i] >= M) {
            tp[nt][k + i] -= M;
          }
          if (tp[nt][k + cv + i] >= M) {
            tp[nt][k + cv + i] -= M;
          }
        }
      }
      swap(t, nt);
    }
    for (int i = 0; i < len; i++) {
      v[i] = tp[t][i];
    }
  }
  void rntt(vector<long long>& v) {
    ntt(v);
    reverse(v.begin() + 1, v.begin() + len);
    for (int i = 0; i < len; i++) {
      v[i] = mul(v[i], invn);
    }
  }
  int size() { return len; }
};
int ntv;
vector<long long> st[2 * MF];
int stz[2 * MF];
NTT bn[LOG];
vector<long long> get(long long l, long long r) {
  vector<long long> res(st[1].size());
  res[0] = 1;
  bn[0].ntt(res);
  int fn = stz[1];
  int sz = 0;
  l += ntv;
  r += ntv;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      for (int i = 0; i < bn[sz].size(); i++) {
        res[i] = mul(res[i], st[l][i]);
      }
      l++;
    }
    if (r & 1) {
      r--;
      for (int i = 0; i < bn[sz].size(); i++) {
        res[i] = mul(res[i], st[r][i]);
      }
    }
    bn[sz].rntt(res);
    sz++;
    bn[sz].ntt(res);
  }
  bn[sz].rntt(res);
  bn[fn].ntt(res);
  return res;
}
long long rf[MF];
long long ff[MF];
void pol(vector<long long>& v, long long val, long long sz, NTT& ntt) {
  vector<long long> x(v.size());
  long long ac = 1;
  for (int i = 0; i < x.size(); i++) {
    if (sz - i >= 0) {
      x[i] = mul(rf[i], ac);
      v[i] = mul(v[i], ff[sz - i]);
    } else {
      v[i] = x[i] = 0;
    }
    ac = mul(ac, val);
  }
  ntt.ntt(v);
  ntt.ntt(x);
  for (int i = 0; i < v.size(); i++) {
    v[i] = mul(v[i], x[i]);
  }
  ntt.rntt(v);
  for (int i = 0; i < v.size(); i++) {
    if (sz - i >= 0) {
      v[i] = mul(v[i], rf[sz - i]);
    } else {
      v[i] = 0;
    }
  }
}
pair<long long, long long> bd[MQ], qd[MQ];
int main() {
  long long n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> w[i];
    w[i] *= -1;
    w[i] = ((w[i] % M) + M) % M;
  }
  for (int i = 0; i < LOG; i++) {
    bn[i] = NTT(2 << i);
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int qv;
    cin >> qv;
    long long q, l, r, d;
    if (qv == 1) {
      cin >> q >> l >> d;
      r = l;
      l--;
      r--;
      d = -w[l] - d;
    } else {
      cin >> q >> l >> r >> d;
      l--;
      r--;
      d *= -1;
    }
    q = ((q % M) + M) % M;
    d = ((d % M) + M) % M;
    qd[i] = {q, d};
    bd[i] = {l, r};
  }
  ntv = 1;
  int mn = 0;
  while (ntv <= max(n, 5LL)) {
    ntv *= 2;
    mn++;
  }
  rf[0] = 1;
  ff[0] = 1;
  for (int i = 1; i < ntv; i++) {
    rf[i] = mul(rf[i - 1], inv(i));
    ff[i] = mul(ff[i - 1], i);
  }
  for (int i = 0; i < ntv; i++) {
    vector<long long> ok(bn[0].size());
    ok[0] = 1;
    if (i < n) {
      ok[1] = w[i];
    } else {
      ok[1] = 0;
    }
    bn[0].ntt(ok);
    st[i + ntv] = ok;
    stz[i + ntv] = 0;
  }
  for (int i = ntv - 1; i > 0; i--) {
    stz[i] = stz[i << 1] + 1;
    vector<long long> ok(bn[stz[i << 1]].size());
    for (int j = 0; j < st[i << 1].size(); j++) {
      ok[j] = mul(st[i << 1][j], st[i << 1 | 1][j]);
    }
    bn[stz[i << 1]].rntt(ok);
    ok.resize(bn[stz[i]].size(), 0);
    bn[stz[i]].ntt(ok);
    st[i] = ok;
  }
  for (int i = 0; i < Q; i++) {
    long long q = qd[i].first, d = qd[i].second, l = bd[i].first,
              r = bd[i].second;
    vector<long long> pa = get(0, l), pb = get(l, r + 1), pc = get(r + 1, n);
    for (int i = 0; i < pa.size(); i++) {
      pa[i] = mul(pa[i], pc[i]);
    }
    long long av = ((q % M) + M) % M, bv = (((q + d) % M) + M) % M;
    long long res = 0;
    bn[mn].rntt(pa);
    bn[mn].rntt(pb);
    pol(pa, av, n - (r - l + 1), bn[mn]);
    pol(pb, bv, (r - l + 1), bn[mn]);
    bn[mn].ntt(pa);
    bn[mn].ntt(pb);
    for (int i = 0; i < pa.size(); i++) {
      pa[i] = mul(pa[i], pb[i]);
    }
    bn[mn].rntt(pa);
    res = pa[k];
    cout << res << '\n';
  }
}