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 S = 65535, mod = 998244353;
vector<int> P[S];
int n, k, a[S], Q, b[S], rev[S], len;
int mo(int x) { return x >= mod ? x - mod : x; }
int qp(int b, int t, int a = 1) {
  for (; t; t >>= 1, b = 1ll * b * b % mod)
    if (t & 1) a = 1ll * a * b % mod;
  return a;
}
void NTT(int* a, int op = 1) {
  for (int i = 1, x; i < len; ++i)
    if (rev[i] > i) x = a[i], a[i] = a[rev[i]], a[rev[i]] = x;
  for (int i = 1; i < len; i <<= 1)
    for (int j = 0, w = qp(3, (mod - 1) / 2 / i * op + mod - 1); j < len;
         j += i << 1)
      for (int k = j, t = 1, x, y; k < j + i; ++k, t = 1ll * t * w % mod)
        x = a[k], y = a[k + i] * 1ll * t % mod, a[k] = mo(x + y),
        a[k + i] = mo(x + mod - y);
  if (op == -1)
    for (int i = 0, iv = qp(len, mod - 2); i < len; ++i)
      a[i] = 1ll * a[i] * iv % mod;
}
void sat(int x) {
  len = 1;
  while (len <= x) len <<= 1;
  for (int i = 0; i < len; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1 ? len >> 1 : 0);
}
void build(int p, int l, int r) {
  P[p].clear();
  if (l == r) {
    P[p].push_back(1);
    P[p].push_back(b[l]);
    return;
  }
  build(p << 1, l, l + r >> 1);
  build(p << 1 | 1, (l + r >> 1) + 1, r);
  int L = P[p << 1].size() + P[p << 1 | 1].size() - 1;
  sat(L);
  static int A[S], B[S];
  P[p].resize(L);
  for (int i = 0; i < len; ++i) A[i] = B[i] = 0;
  for (int i = P[p << 1].size() - 1; ~i; --i) A[i] = P[p << 1][i];
  for (int i = P[p << 1 | 1].size() - 1; ~i; --i) B[i] = P[p << 1 | 1][i];
  NTT(A);
  NTT(B);
  for (int i = 0; i < len; ++i) A[i] = 1ll * A[i] * B[i] % mod;
  NTT(A, -1);
  for (int i = 0; i < L; ++i) P[p][i] = A[i];
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  scanf("%d", &Q);
  for (int i = 1, o, l, r, d, q; i <= Q; ++i) {
    scanf("%d", &o);
    if (o == 1) {
      scanf("%d%d%d", &q, &l, &d);
      for (int i = 1; i <= n; ++i) b[i] = mo(q - a[i] + mod);
      b[l] = mo(q - d + mod);
    } else {
      scanf("%d%d%d%d", &q, &l, &r, &d);
      for (int i = 1; i <= n; ++i)
        b[i] = mo(mo(mod + q - a[i]) + mod - (l <= i && i <= r ? d : 0));
    }
    build(1, 1, n);
    printf("%d\n", P[1][k]);
  }
}