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 mod = 998244353;
const int maxn = 2e4 + 10;
inline long long qpow(long long x, long long n) {
  long long ret = 1ll;
  while (n) {
    if (n % 2) ret = ret * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}
long long A[maxn];
int N, K, Q;
vector<vector<long long>> poly;
void change(vector<long long>& y, int len) {
  int i, j, k;
  for (i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    k = len / 2;
    while (j >= k) {
      j = j - k;
      k = k / 2;
    }
    if (j < k) j += k;
  }
}
void NTT(vector<long long>& P, int op) {
  int len = P.size(), i, j, k;
  change(P, len);
  for (i = 1; i < len; i <<= 1) {
    long long gn = qpow(3ll, (mod - 1) / (i << 1));
    if (op == -1) gn = qpow(gn, mod - 2);
    for (j = 0; j < len; j += (i << 1)) {
      long long g = 1;
      for (k = 0; k < i; ++k, g = g * gn % mod) {
        long long x = P[j + k], y = g * P[j + k + i] % mod;
        P[j + k] = (x + y) % mod;
        P[j + k + i] = (x - y + mod) % mod;
      }
    }
  }
  if (op == -1) {
    long long inv = qpow(len, mod - 2);
    for (i = 0; i < len; ++i) P[i] = P[i] * inv % mod;
  }
}
vector<long long> multiply(const vector<long long>& aa,
                           const vector<long long>& bb) {
  int n = aa.size(), m = bb.size(), len = 1, i;
  while (len < 2 * n || len < 2 * m) len <<= 1;
  vector<long long> a(len), b(len);
  for (i = 0; i < n; ++i) a[i] = aa[i];
  for (i = 0; i < m; ++i) b[i] = bb[i];
  if (0) {
    printf("show a : ");
    for (long long i : a) printf("%lld ", i);
    printf("\n");
    printf("show b : ");
    for (long long i : b) printf("%lld ", i);
    printf("\n");
  }
  NTT(a, 1);
  NTT(b, 1);
  if (0) {
    printf("show a : ");
    for (long long i : a) printf("%lld ", i);
    printf("\n");
    printf("show b : ");
    for (long long i : b) printf("%lld ", i);
    printf("\n");
  }
  vector<long long> c(len);
  for (i = 0; i < len; ++i) c[i] = a[i] * b[i] % mod;
  NTT(c, -1);
  if (0) {
    printf("show c : ");
    for (long long i : c) printf("%lld ", i);
    printf("\n");
  }
  return c;
}
vector<long long> cal(int l, int r) {
  if (l == r) {
    vector<long long> ret;
    for (long long i : poly[l]) ret.push_back(i);
    return ret;
  }
  int mid = (l + r) >> 1;
  return multiply(cal(l, mid), cal(mid + 1, r));
}
long long solve(int q) {
  poly = vector<vector<long long>>();
  for (int i = 1; i <= N; ++i) {
    vector<long long> vi = {1ll, (long long)q - A[i]};
    poly.push_back(vi);
  }
  if (0) {
    printf("show poly : ");
    for (int i = 0; i < poly.size(); ++i) {
      printf("at %d : ", i);
      for (long long j : poly[i]) printf("%lld ", j);
      printf("\n");
    }
  }
  vector<long long> ret = cal(0, N - 1);
  return (ret[K] % mod + mod) % mod;
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%lld", &A[i]);
  }
  scanf("%d", &Q);
  while (Q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int q, i, d;
      scanf("%d %d %d", &q, &i, &d);
      long long Ai = A[i];
      A[i] = d;
      printf("%lld\n", solve(q));
      A[i] = Ai;
    }
    if (t == 2) {
      int q, L, R, d;
      scanf("%d %d %d %d", &q, &L, &R, &d);
      for (int i = L; i <= R; ++i) A[i] += d;
      printf("%lld\n", solve(q));
      for (int i = L; i <= R; ++i) A[i] -= d;
    }
  }
}
