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;
template <class T, class V>
ostream &operator<<(ostream &s, pair<T, V> a) {
  s << a.first + 1 << ' ' << a.second + 1;
  return s;
}
struct NTT {
  long long int MD, M = 1, R;
  vector<int> r;
  vector<long long int> w[2];
  long long int bigmod(long long int a, long long int p, long long int m) {
    long long int res = 1, x = a;
    while (p) {
      if (p & 1) res = (res * x) % m;
      x = (x * x) % m;
      p >>= 1;
    }
    return res;
  }
  long long int primitive_root(int n) {
    int p = n - 1;
    vector<int> d;
    for (int i = 2; i * i <= p; i++) {
      if (p % i == 0) {
        d.push_back(i);
        while (p % i == 0) p /= i;
      }
    }
    if (p > 1) d.push_back(p);
    for (int i = 2; i <= n; i++) {
      bool ok = true;
      for (auto x : d) ok &= (bigmod(i, (n - 1) / x, n) != 1);
      if (ok) return i;
    }
    assert(false);
  }
  NTT(long long int n, long long int _MD) : MD(_MD) {
    int u = 0;
    while (M < n) M <<= 1, u++;
    r.resize(M);
    w[0].resize(M, 1);
    w[1].resize(M, 1);
    R = 3;
    w[0][1] = bigmod(R, (MD - 1) / M, MD);
    w[1][1] = bigmod(w[0][1], MD - 2, MD);
    for (int i = 1; i < M; i++) {
      int l = __builtin_ctz(i);
      r[i] = r[i ^ (1 << l)] | (1 << (u - l - 1));
      w[0][i] = w[0][i - 1] * w[0][1] % MD;
      w[1][i] = w[1][i - 1] * w[1][1] % MD;
    }
  }
  void fft(vector<long long int> &a, bool inv = false) {
    for (int i = 0; i < M; i++)
      if (i < r[i]) swap(a[i], a[r[i]]);
    for (int len = 2; len <= M; len <<= 1) {
      for (int i = 0, inc = M / len; i < M; i += len) {
        for (int j = 0, l = 0; j < (len >> 1); j++, l += inc) {
          long long int u = a[i + j],
                        v = a[i + j + (len >> 1)] * w[inv][l] % MD;
          a[i + j] = (u + v >= MD ? u + v - MD : u + v);
          a[i + j + (len >> 1)] = (u < v ? u - v + MD : u - v);
        }
      }
    }
    if (inv) {
      long long int r = bigmod(M, MD - 2, MD);
      for (auto &x : a) x = x * r % MD;
    }
  }
  vector<long long int> multiply(vector<long long int> &a,
                                 vector<long long int> &b) {
    vector<long long int> v1(M), v2(M);
    for (int i = 0; i < a.size(); i++) v1[i] = a[i];
    for (int i = 0; i < b.size(); i++) v2[i] = b[i];
    fft(v1);
    fft(v2);
    for (int i = 0; i < M; i++) v1[i] = v1[i] * v2[i] % MD;
    fft(v1, 1);
    return v1;
  }
  vector<long long int> POWER(vector<long long int> &a, long long int n) {
    vector<long long int> v1(M);
    for (int i = 0; i < a.size(); i++) v1[i] = a[i];
    fft(v1);
    for (int i = 0; i < M; i++) v1[i] = bigmod(v1[i], n, MD);
    fft(v1, 1);
    return v1;
  }
};
long long int ara[200005];
long long int K;
vector<long long int> solve(long long int l, long long int r) {
  if (l == r) {
    vector<long long int> t(2, 1);
    t[1] = ara[l];
    return t;
  }
  vector<long long int> t1 = solve(l, (l + r) / 2);
  vector<long long int> t2 = solve((l + r) / 2 + 1, r);
  if (t1.size() > K + 1) t1.resize(K + 1);
  if (t2.size() > K + 1) t2.resize(K + 1);
  NTT nt(t1.size() + t2.size(), (998244353));
  return nt.multiply(t1, t2);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int qq = 1; qq <= T; qq++) {
    int n;
    cin >> n >> K;
    for (int i = 0; i < n; i++) cin >> ara[i];
    long long int Q;
    cin >> Q;
    while (Q--) {
      long long int t, q, l, r, d;
      cin >> t >> q;
      if (t == 1) {
        cin >> l >> d;
        long long int pre = ara[l - 1];
        ara[l - 1] = d;
        for (int i = 0; i < n; i++)
          ara[i] = (q - ara[i] + (998244353)) % (998244353);
        cout << solve(0, n - 1)[K] << endl;
        for (int i = 0; i < n; i++)
          ara[i] = (q - ara[i] + (998244353)) % (998244353);
        ara[l - 1] = pre;
      } else {
        cin >> l >> r >> d;
        for (int i = l - 1; i < r; i++) ara[i] = (ara[i] + d) % (998244353);
        for (int i = 0; i < n; i++)
          ara[i] = (q - ara[i] + (998244353)) % (998244353);
        cout << solve(0, n - 1)[K] << endl;
        for (int i = 0; i < n; i++)
          ara[i] = (q - ara[i] + (998244353)) % (998244353);
        for (int i = l - 1; i < r; i++)
          ara[i] = (ara[i] - d + (998244353)) % (998244353);
      }
    }
  }
}