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;
inline int read() {
  register int r = 0, c = 0;
  for (; c < '-'; c = getchar())
    ;
  for (; c > '-'; r = r * 10 + c - '0', c = getchar())
    ;
  return r;
}
long long modPow(long long a, long long b, long long p) {
  if ((b & 1) == 1) return a * modPow(a, b - 1, p) % p;
  if (b == 0) return 1 % p;
  return modPow(a * a % p, b / 2, p);
}
template <class T>
void bitReverse(vector<T>& vec) {
  int n = vec.size();
  int lg = 0;
  while ((1 << lg) < n) ++lg;
  for (int i = 0; i < n; ++i) {
    int t = 0;
    for (int j = 0; j < lg; ++j) {
      if (i & (1 << j)) t |= 1 << (lg - 1 - j);
    }
    if (i < t) swap(vec[i], vec[t]);
  }
}
template <int P>
void ntt(vector<int>& pol, bool inv) {
  bitReverse(pol);
  int n = pol.size();
  int lg = 0;
  while ((1 << lg) < n) ++lg;
  long long nth_root = modPow(3, (P - 1) / n, P);
  if (inv) nth_root = modPow(nth_root, n - 1, P);
  vector<long long> pows(lg, nth_root);
  for (int i = lg - 2; i >= 0; --i) pows[i] = (pows[i + 1] * pows[i + 1]) % P;
  long long tmp = 1;
  for (int i = 0; i < n; ++i) tmp = (tmp * nth_root) % P;
  for (lg = 0; (1 << lg) < n; ++lg) {
    int h = 1 << lg;
    int len = h << 1;
    long long root = pows[lg];
    for (int j = 0; j < n; j += len) {
      long long curr = 1;
      for (int i = j; i < j + h; ++i) {
        int tmp = (curr * pol[i + h]) % P;
        curr = (curr * root) % P;
        pol[i + h] = P - tmp + pol[i];
        if (pol[i + h] >= P) pol[i + h] -= P;
        pol[i] += tmp;
        if (pol[i] >= P) pol[i] -= P;
      }
    }
  }
}
template <int P>
vector<int> polyMult(vector<int> a, vector<int> b) {
  int as = a.size();
  int bs = b.size();
  int n = 1;
  while (n < (as + bs)) n <<= 1;
  a.resize(n, 0);
  b.resize(n, 0);
  ntt<P>(a, false);
  ntt<P>(b, false);
  vector<int> c(n);
  int n_inv = modPow(n, P - 2, P);
  for (int i = 0; i < n; ++i) {
    long long prod = (long long)a[i] * b[i] % P;
    c[i] = prod * n_inv % P;
  }
  ntt<P>(c, true);
  c.resize(as + bs - 1);
  return c;
}
const int MOD = 998244353;
vector<int> s, v;
int N, K;
vector<int> slove(int l, int r) {
  if (l == r) {
    vector<int> a(2);
    a[0] = 1;
    a[1] = v[l - 1];
    return a;
  }
  vector<int> v =
      polyMult<MOD>(slove(l, l + r >> 1), slove((l + r >> 1) + 1, r));
  if (v.size() > K + 1) v.resize(K + 1);
  return v;
}
int main() {
  N = read();
  K = read();
  for (int i = 1; i <= N; i++) {
    s.push_back(read());
  }
  int T = read();
  for (int i = 1; i <= T; i++) {
    int op = read();
    v.clear();
    if (op == 1) {
      int q = read(), a = read(), d = read();
      for (int i = 1; i <= N; i++) {
        if (i == a)
          v.push_back(q - d);
        else
          v.push_back(((q - s[i - 1]) % MOD + MOD) % MOD);
      }
    } else {
      int q = read(), l = read(), r = read(), d = read();
      for (int i = 1; i <= N; i++) {
        if (i >= l && i <= r) {
          v.push_back(((q - s[i - 1] - d) % MOD + MOD) % MOD);
        } else
          v.push_back(((q - s[i - 1]) % MOD + MOD) % MOD);
      }
    }
    printf("%d\n", (slove(1, N)[K] % MOD + MOD) % MOD);
  }
}