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;
int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x;
}
const int N = 66006;
int Pow_mod(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = 1ll * ret * x % 998244353;
    x = 1ll * x * x % 998244353;
    y >>= 1;
  }
  return ret;
}
int Minus(int x, int y) { return x >= y ? x - y : x - y + 998244353; }
int Plus(int x, int y) {
  return x + y >= 998244353 ? x + y - 998244353 : x + y;
}
int L, R[N], x[N];
void ntt(int *A, int ty) {
  for (int i = 0; i < L; i++) x[R[i]] = A[i];
  for (int i = 0; i < L; i++) A[i] = x[i];
  for (int i = 2; i <= L; i <<= 1) {
    int wn = Pow_mod(3, (998244353 - 1) / i);
    if (ty == -1) wn = Pow_mod(wn, 998244353 - 2);
    for (int j = 0; j < L; j += i) {
      int w = 1;
      for (int k = j; k < j + i / 2; k++) {
        int t = 1ll * w * A[k + i / 2] % 998244353;
        A[k + i / 2] = Minus(A[k], t);
        A[k] = Plus(A[k], t);
        w = 1ll * w * wn % 998244353;
      }
    }
  }
  if (ty == 1) return;
  int invl = Pow_mod(L, 998244353 - 2);
  for (int i = 0; i < L; i++) A[i] = 1ll * A[i] * invl % 998244353;
}
int n, K, a[N], b[N];
int ans[N], aa[N], bb[N];
void work(int l, int r) {
  if (l == r) {
    ans[l] = b[l];
    return;
  }
  int len = (r - l + 1), mid = (l + r) >> 1;
  work(l, mid);
  work(mid + 1, r);
  L = 1;
  while (L <= len) L <<= 1;
  for (int i = 1; i < L; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) * (L >> 1));
  for (int i = 1; i <= mid - l + 1; i++) aa[i] = ans[l + i - 1];
  aa[0] = 1;
  for (int i = 1; i <= r - mid; i++) bb[i] = ans[mid + i];
  bb[0] = 1;
  ntt(aa, 1);
  ntt(bb, 1);
  for (int i = 0; i < L; i++) aa[i] = 1ll * aa[i] * bb[i] % 998244353;
  ntt(aa, -1);
  for (int i = 1; i <= len; i++) ans[l + i - 1] = aa[i];
  for (int i = 0; i < L; i++) aa[i] = bb[i] = 0;
}
int main() {
  n = read();
  K = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  int Q, opt, l, r, q, d;
  Q = read();
  while (Q--) {
    opt = read();
    q = read();
    if (opt == 1) {
      l = read();
      d = read();
      for (int i = 1; i <= n; i++) b[i] = Minus(q, a[i]);
      b[l] = Minus(q, d);
      work(1, n);
      printf("%d\n", ans[K]);
    } else {
      l = read();
      r = read();
      d = read();
      for (int i = 1; i <= n; i++) b[i] = Minus(q, a[i]);
      for (int i = l; i <= r; i++) b[i] = Minus(b[i], d);
      work(1, n);
      printf("%d\n", ans[K]);
    }
  }
  return 0;
}