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 MOD = 998244353;
int a[20005], b[20005];
struct FFTmod {
  const static int LOGN = 16;
  const static int MAXN = 1 << LOGN;
  const double PI = acos(-1);
  int lg2(int n) { return 32 - __builtin_clz(n - 1); }
  int rev[MAXN];
  complex<double> rt[MAXN];
  void precalc() {
    rt[1] = complex<double>{1, 0};
    for (int k = 2; k < MAXN; k *= 2) {
      complex<double> z[] = {1, polar(1.0, PI / k)};
      for (int i = k; i < 2 * k; i++) rt[i] = rt[i / 2] * z[i & 1];
    }
  }
  void fft(complex<double> *a, int n) {
    for (int i = 0; i < n; i++) rev[i] = (rev[i / 2] | (i & 1) << lg2(n)) / 2;
    for (int i = 0; i < n; i++)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2)
      for (int i = 0; i < n; i += 2 * k)
        for (int j = 0; j < k; j++) {
          auto x = (double *)&rt[j + k], y = (double *)&a[i + j + k];
          complex<double> z(x[0] * y[0] - x[1] * y[1],
                            x[0] * y[1] + x[1] * y[0]);
          a[i + j + k] = a[i + j] - z;
          a[i + j] += z;
        }
  }
  complex<double> X[2][MAXN], Y[2][MAXN];
  vector<long long> multiply(const vector<long long> &a,
                             const vector<long long> &b) {
    int cut = sqrt(MOD), sz = a.size() + b.size() - 1;
    int n = 1 << lg2(sz);
    fill(X[0], X[0] + n, complex<double>{0, 0}),
        fill(X[1], X[1] + n, complex<double>{0, 0});
    vector<long long> res(sz);
    for (int i = 0; i < a.size(); i++)
      X[0][i] = {(double)(a[i] / cut), (double)(a[i] % cut)};
    for (int i = 0; i < b.size(); i++)
      X[1][i] = {(double)(b[i] / cut), (double)(b[i] % cut)};
    fft(X[0], n), fft(X[1], n);
    for (int i = 0; i < n; i++) {
      int j = (n - i) & (n - 1);
      complex<double> fl = (X[0][i] + conj(X[0][j])) * complex<double>{0.5, 0},
                      fs = (X[0][i] - conj(X[0][j])) * complex<double>{0, -0.5},
                      gl = (X[1][i] + conj(X[1][j])) * complex<double>{0.5, 0},
                      gs = (X[1][i] - conj(X[1][j])) * complex<double>{0, -0.5};
      Y[0][-i & (n - i)] = (fl * gl) + (fl * gs) * complex<double>{0, 1};
      Y[1][-i & (n - i)] = (fs * gl) + (fs * gs) * complex<double>{0, 1};
    }
    fft(Y[0], n), fft(Y[1], n);
    for (int i = 0; i < sz; i++) {
      Y[0][i] /= n, Y[1][i] /= n;
      long long av = round(Y[0][i].real());
      long long bv = round(Y[0][i].imag()) + round(Y[1][i].real());
      long long cv = round(Y[1][i].imag());
      av %= MOD, bv %= MOD, cv %= MOD;
      res[i] = av * cut * cut + bv * cut + cv;
      res[i] = (res[i] % MOD + MOD) % MOD;
    }
    return res;
  }
} fft;
vector<long long> poly[20005];
vector<long long> solve(int s, int e) {
  if (s == e)
    return poly[s];
  else {
    int mid = (s + e) / 2;
    return fft.multiply(solve(s, mid), solve(mid + 1, e));
  }
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  fft.precalc();
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int q, i, d;
      scanf("%d%d%d", &q, &i, &d);
      for (int i = 1; i <= n; i++) b[i] = (q - a[i] + MOD) % MOD;
      b[i] = (q - d + MOD) % MOD;
      for (int i = 1; i <= n; i++) {
        poly[i].clear();
        poly[i].emplace_back(1);
        poly[i].emplace_back(b[i]);
      }
      printf("%d\n", solve(1, n)[k]);
    } else {
      int q, l, r, d;
      scanf("%d%d%d%d", &q, &l, &r, &d);
      for (int i = 1; i <= n; i++) {
        if (l <= i && i <= r)
          b[i] = (q - (a[i] + d) + MOD) % MOD;
        else
          b[i] = (q - a[i] + MOD) % MOD;
      }
      for (int i = 1; i <= n; i++) {
        poly[i].clear();
        poly[i].emplace_back(1);
        poly[i].emplace_back(b[i]);
      }
      printf("%d\n", solve(1, n)[k]);
    }
  }
}