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 int mod = 998244353;
const int prm = 3;
const int N = 2e4 + 10;
inline int fpow(int a, int b, int m) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % m;
    a = 1ll * a * a % m;
    b >>= 1;
  }
  return ret;
}
struct NTT {
  int n;
  int a[N << 2], b[N << 2];
  int gn, g, x, y;
  void init(int len) {
    for (n = 1; n <= len; n <<= 1)
      ;
    for (int i = 0; i < n; i++) a[i] = b[i] = 0;
  }
  void input(int* a, int* b, int len) {
    for (int i = 0; i < len; i++) a[i] = b[i];
  }
  void output(int* a, int* b, int len) {
    for (int i = 0; i < len; i++) b[i] = a[i];
  }
  void ntt(int* a, int opt) {
    for (int i = 0, j = 0, k; i < n; i++) {
      if (i > j) swap(a[i], a[j]);
      for (k = n / 2; (j ^= k) < k; k >>= 1)
        ;
    }
    for (int i = 1; i < n; i <<= 1) {
      gn = fpow(prm, (mod - 1) / (i * 2), mod);
      if (opt == -1) gn = fpow(gn, mod - 2, mod);
      for (int j = 0; j < n; j += i << 1) {
        g = 1;
        for (int k = j; k < j + i; k++) {
          x = a[k], y = 1ll * g * a[k + i] % mod;
          a[k] = (x + y) % mod;
          a[k + i] = (x + mod - y) % mod;
          g = 1ll * g * gn % mod;
        }
      }
    }
  }
  void calculate(void) {
    ntt(a, 1);
    ntt(b, 1);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a, -1);
    int t = fpow(n, mod - 2, mod);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * t % mod;
  }
  vector<int> v[N];
  int coef[N];
  void solve(int st, int en, int p) {
    if (st == en) {
      v[p].push_back(1);
      v[p].push_back((coef[st] % mod + mod) % mod);
      return;
    }
    int md = (st + en) >> 1;
    solve(st, md, p);
    solve(md + 1, en, p + 1);
    init(en - st + 1 + 1);
    for (int i = 0; i <= md - st + 1; i++) a[i] = v[p][i];
    for (int i = 0; i <= en - md; i++) b[i] = v[p + 1][i];
    calculate();
    v[p].clear();
    v[p + 1].clear();
    for (int i = 0; i <= en - st + 1; i++) v[p].push_back(a[i]);
  }
} F;
int a[N];
int b[N];
int main(void) {
  int n, k, qq;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  int opt, q, i, l, r, d;
  scanf("%d", &qq);
  while (qq--) {
    F.v[0].clear();
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d%d%d", &q, &i, &d);
      for (int j = 1; j <= n; j++) {
        F.coef[j] = q - (i == j ? d : a[j]);
      }
      F.solve(1, n, 0);
      printf("%d\n", F.v[0][k]);
    } else {
      scanf("%d%d%d%d", &q, &l, &r, &d);
      for (int j = 1; j <= n; j++) {
        F.coef[j] = q - a[j] - ((l <= j && j <= r) ? d : 0);
      }
      F.solve(1, n, 0);
      printf("%d\n", F.v[0][k]);
    }
  }
}
