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;
const int M = 2e6 + 10;
int a[M], b[M], c[M], d[M], e[M], f[M], F[M];
vector<int> T[M];
struct NTT {
  static const int G = 3, P = 998244353;
  int N, na, nb, w[2][M], rev[M];
  long long kpow(long long a, int b) {
    long long c = 1;
    for (; b; b >>= 1, a = a * a % P)
      if (b & 1) c = c * a % P;
    return c;
  }
  void FFT(int *a, int f) {
    for (int i = (0); i < (N); i++)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < N; i <<= 1)
      for (int j = 0, t = N / (i << 1); j < N; j += i << 1)
        for (int k = 0, l = 0, x, y; k < i; k++, l += t)
          x = (long long)w[f][l] * a[j + k + i] % P, y = a[j + k],
          a[j + k] = (y + x) % P, a[j + k + i] = (y - x + P) % P;
    if (f)
      for (int i = 0, x = kpow(N, P - 2); i < N; i++)
        a[i] = (long long)a[i] * x % P;
  }
  void work() {
    int d = __builtin_ctz(N);
    w[0][0] = w[1][0] = 1;
    for (int i = 1, x = kpow(G, (P - 1) / N), y = kpow(x, P - 2); i < N; i++) {
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (d - 1));
      w[0][i] = (long long)x * w[0][i - 1] % P,
      w[1][i] = (long long)y * w[1][i - 1] % P;
    }
  }
  void doit(int *a, int *b, int na, int nb) {
    for (N = 1; N < na + nb - 1; N <<= 1)
      ;
    for (int i = (na); i < (N); i++) a[i] = 0;
    for (int i = (nb); i < (N); i++) b[i] = 0;
    work(), FFT(a, 0), FFT(b, 0);
    for (int i = (0); i < (N); i++) a[i] = (long long)a[i] * b[i] % P;
    FFT(a, 1);
  }
  void get_inv(int *a, int *b, int na) {
    if (na == 1) {
      b[0] = kpow(a[0], P - 2);
      return;
    }
    get_inv(a, b, (na + 1) >> 1);
    for (N = 1; N < (na << 1); N <<= 1)
      ;
    work();
    for (int i = (0); i < (na); i++) c[i] = a[i];
    for (int i = (na); i < (N); i++) c[i] = 0;
    FFT(c, 0), FFT(b, 0);
    for (int i = (0); i < (N); i++)
      b[i] = 1ll * (2 - 1ll * c[i] * b[i] % P + P) % P * b[i] % P;
    FFT(b, 1);
    for (int i = (na); i < (N); i++) b[i] = 0;
  }
  void get_ln(int *a, int *b, int na) {
    for (int i = (0); i < (na - 1); i++)
      d[i] = (long long)(a[i + 1]) * (i + 1) % P;
    for (int i = (na); i < (N); i++) d[i] = 0;
    d[na - 1] = 0;
    get_inv(a, b, na);
    doit(b, d, na, na);
    for (int i = (na)-1; i >= (1); i--)
      b[i] = (long long)b[i - 1] * kpow(i, P - 2) % P;
    b[0] = 0;
  }
  void get_exp(int *a, int *b, int na) {
    if (na == 1) {
      b[0] = 1;
      return;
    }
    get_exp(a, b, (na + 1) >> 1);
    for (int i = 0; i < (na << 1); i++) f[i] = 0;
    get_ln(b, f, na);
    for (N = 1; N < (na << 1); N <<= 1)
      ;
    work();
    f[0] = ((long long)a[0] + 1 - f[0] + P) % P;
    for (int i = (1); i < (na); i++) f[i] = ((long long)a[i] - f[i] + P) % P;
    FFT(f, 0);
    FFT(b, 0);
    for (int i = (0); i < (N); i++) b[i] = (long long)b[i] * f[i] % P;
    FFT(b, 1);
    for (int i = (na); i < (N); i++) b[i] = f[i] = 0;
  }
  void get_pow(int *a, int *b, int na, int k) {
    get_ln(a, e, na);
    for (int i = (0); i < (na); i++) e[i] = (long long)e[i] * k % P;
    get_exp(e, b, na);
  }
  void fast_pow(int *a, int *b, int na, int k, int maxn) {
    for (N = 1; N < max(((maxn + 1) << 1), (na << 1)); N <<= 1)
      ;
    for (int i = (na); i < (N); i++) a[i] = 0;
    for (int i = (0); i < (N); i++) b[i] = 0;
    b[0] = 1;
    work();
    while (k) {
      FFT(a, 0);
      if (k & 1) {
        FFT(b, 0);
        for (int i = (0); i < (N); i++) b[i] = (long long)a[i] * b[i] % P;
        FFT(b, 1);
        for (int i = (max(na, maxn + 1)); i < (N); i++) b[i] = 0;
      }
      for (int i = (0); i < (N); i++) a[i] = (long long)a[i] * a[i] % P;
      FFT(a, 1);
      for (int i = (max(na, maxn + 1)); i < (N); i++) a[i] = 0;
      k >>= 1;
    }
  }
  priority_queue<pair<int, int> > H;
  void Merge(int m) {
    while (!H.empty()) H.pop();
    for (int i = (0); i < (m); i++) H.emplace(make_pair(-T[i].size(), i));
    while (H.size() >= 2) {
      int x = H.top().second;
      H.pop();
      int y = H.top().second;
      H.pop();
      for (int i = (0); i < (T[x].size()); i++) a[i] = T[x][i];
      for (int i = (0); i < (T[y].size()); i++) b[i] = T[y][i];
      doit(a, b, T[x].size(), T[y].size());
      int na = T[x].size() + T[y].size();
      T[x].clear();
      T[y].clear();
      for (int i = (0); i < (na); i++) T[x].push_back(a[i]);
      H.emplace(-T[x].size(), x);
    }
  }
} ntt;
long long mod = 998244353;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = (0); i < (n); i++) cin >> F[i];
  int Q;
  cin >> Q;
  while (Q--) {
    for (int i = (0); i < (n); i++) T[i].clear();
    for (int i = (0); i < (n); i++) T[i].push_back(1);
    int op, q;
    cin >> op >> q;
    if (op == 1) {
      int id, d;
      cin >> id >> d;
      for (int i = (0); i < (n); i++) {
        if (i == id - 1)
          T[i].push_back((q - d + mod) % mod);
        else
          T[i].push_back((q - F[i] + mod) % mod);
      }
    } else {
      int L, R, d;
      cin >> L >> R >> d;
      for (int i = (0); i < (n); i++) {
        if (i >= L - 1 && i <= R - 1)
          T[i].push_back(((q - F[i] - d) % mod + mod) % mod);
        else
          T[i].push_back((q - F[i] + mod) % mod);
      }
    }
    ntt.Merge(n);
    cout << T[ntt.H.top().second][k] << "\n";
  }
  return 0;
}