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 long long M = 998244353;
long long pwr(long long a, long long b, long long m = M) {
  long long ret = 1;
  while (b > 0) {
    if (b & 1) ret = ret * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return ret;
}
template <long long MOD = 1000000007>
struct Modular {
  long long value;
  static const long long MOD_value = MOD;
  Modular(long long v = 0) {
    value = v % MOD;
    if (value < 0) value += MOD;
  }
  Modular(long long a, long long b) : value(0) {
    *this += a;
    *this /= b;
  }
  Modular& operator+=(Modular const& b) {
    value += b.value;
    if (value >= MOD) value -= MOD;
    return *this;
  }
  Modular& operator-=(Modular const& b) {
    value -= b.value;
    if (value < 0) value += MOD;
    return *this;
  }
  Modular& operator*=(Modular const& b) {
    value = (long long)value * b.value % MOD;
    return *this;
  }
  friend Modular mexp(Modular a, long long e) {
    Modular res = 1;
    while (e) {
      if (e & 1) res *= a;
      a *= a;
      e >>= 1;
    }
    return res;
  }
  friend Modular inverse(Modular b, long long m = MOD) {
    long long u = 0, v = 1, a = b.value;
    while (a != 0) {
      long long t = m / a;
      m -= t * a;
      swap(a, m);
      u -= t * v;
      swap(u, v);
    }
    return Modular(u);
  }
  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {
    return os << a.value;
  }
  friend bool operator==(Modular const& a, Modular const& b) {
    return a.value == b.value;
  }
  friend bool operator!=(Modular const& a, Modular const& b) {
    return a.value != b.value;
  }
};
using mint = Modular<M>;
void ntt(vector<mint>& a, bool invert) {
  long long n = a.size();
  for (long long i = 1, j = 0, bit; i < n; i++) {
    for (bit = n >> 1; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (long long len = 2; len <= n; len <<= 1) {
    long long wlen = pwr(3, (M - 1) / len);
    if (invert) wlen = pwr(wlen, M - 2);
    for (long long i = 0; i < n; i += len) {
      mint w = 1;
      for (long long j = 0; j < len / 2; j++) {
        mint u = a[i + j], v = a[i + j + len / 2] * w;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        w *= wlen;
      }
    }
  }
  if (invert) {
    for (mint& x : a) x /= n;
  }
}
vector<mint>& multiply(vector<mint>& a, vector<mint>& b) {
  long long n = 1;
  while (n < (long long)(a.size() + b.size())) n *= 2;
  a.resize(n);
  b.resize(n);
  ntt(a, 0);
  ntt(b, 0);
  for (long long i = 0; i < n; ++i) a[i] *= b[i];
  ntt(a, 1);
  return a;
}
void solve(vector<mint>& a) {
  long long n = a.size();
  if (n == 1) {
    a.insert(a.begin(), 1);
    return;
  }
  vector<mint> l(a.begin(), a.begin() + n / 2), r(a.begin() + n / 2, a.end());
  solve(l);
  solve(r);
  a = multiply(l, r);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  long long n, k, s = 1;
  cin >> n >> k;
  vector<long long> a(n);
  for (long long i = 0; i < n; ++i) cin >> a[i];
  while (s < n) s *= 2;
  long long q;
  cin >> q;
  while (q--) {
    long long c, sub;
    cin >> c >> sub;
    vector<mint> b(a.begin(), a.end());
    b.resize(s, 0);
    if (c == 1) {
      long long id, d;
      cin >> id >> d;
      b[id - 1] = d;
    } else {
      long long l, r, d;
      cin >> l >> r >> d;
      for (long long i = l - 1; i < r; ++i) b[i] += d;
    }
    for (long long i = 0; i < n; ++i) b[i] = sub - b[i];
    solve(b);
    cout << b[k] << '\n';
  }
}
