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 n, K, b[40004], a[40004];
int Wl, Wl2, w[40004], lg[40004], inv[40004] = {1, 1};
int Pow(int b, int k) {
  int r = 1;
  for (; k; k >>= 1, b = 1ll * b * b % 998244353)
    if (k & 1) r = 1ll * r * b % 998244353;
  return r;
}
void init(int n) {
  for (Wl = 1; n >= Wl << 1; Wl <<= 1)
    ;
  int pw = Pow(3, (998244353 - 1) / (Wl2 = Wl << 1));
  w[Wl] = 1;
  for (int i = (Wl + 1), LIM = (Wl2 - 1); i <= LIM; i++)
    w[i] = 1ll * w[i - 1] * pw % 998244353;
  for (int i = (Wl - 1), LIM = (1); i >= LIM; i--) w[i] = w[i << 1];
  for (int i = (2), LIM = (Wl2); i <= LIM; i++)
    inv[i] = 1ll * (998244353 - 998244353 / i) * inv[998244353 % i] % 998244353,
    lg[i] = lg[i >> 1] + 1;
}
void NTT(int *A, int n, int tp) {
  static int r[40004];
  static unsigned long long a[40004];
  if (tp ^ 1) reverse(A + 1, A + n);
  for (int i = (0), LIM = (n - 1); i <= LIM; i++)
    r[i] = r[i >> 1] >> 1 | (i & 1) << (lg[n] - 1),
    a[i] = (A[r[i]] += A[r[i]] >> 31 & 998244353);
  for (int L = 1; L < n; L <<= 1)
    for (int s = 0, L2 = L << 1; s < n; s += L2)
      for (int k = s, x = L, t; k < s + L; k++, x++)
        t = w[x] * a[k + L] % 998244353, a[k + L] = a[k] - t + 998244353,
        a[k] += t;
  for (int i = (0), LIM = (n - 1); i <= LIM; i++) A[i] = a[i] % 998244353;
  if (tp ^ 1)
    for (int i = (0), LIM = (n - 1); i <= LIM; i++)
      A[i] = 1ll * A[i] * inv[n] % 998244353;
}
void Mul(int *A, int *B, int *C, int n, int m) {
  static int st[2][40004];
  int L = 1 << lg[n + m] + 1;
  for (int i = (0), LIM = (L - 1); i <= LIM; i++)
    st[0][i] = i <= n ? A[i] : 0, st[1][i] = i <= m ? B[i] : 0;
  NTT(st[0], L, 1), NTT(st[1], L, 1);
  for (int i = (0), LIM = (L - 1); i <= LIM; i++)
    C[i] = 1ll * st[0][i] * st[1][i] % 998244353;
  NTT(C, L, -1);
}
int *f[40004 << 2];
void Build(int u, int l, int r) {
  f[u] = new int[1 << lg[r - l + 1] + 1];
  if (l == r) return;
  int m = l + r >> 1;
  Build(u << 1, l, m), Build(u << 1 | 1, m + 1, r);
}
void Sol(int u, int l, int r) {
  memset(f[u], 0, 4 * (1 << lg[r - l + 1] + 1));
  if (l == r) return (void)(f[u][0] = 1, f[u][1] = b[l]);
  int m = l + r >> 1;
  Sol(u << 1, l, m), Sol(u << 1 | 1, m + 1, r);
  Mul(f[u << 1], f[u << 1 | 1], f[u], m - l + 1, r - m);
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = (1), LIM = (n); i <= LIM; i++) scanf("%d", &a[i]);
  init(n);
  int Q;
  scanf("%d", &Q);
  Build(1, 1, n);
  for (int op, q, i, d, l, r; Q--;) {
    scanf("%d", &op);
    memcpy(b, a, sizeof b);
    if (op == 1) {
      scanf("%d%d%d", &q, &i, &d);
      b[i] = d;
    } else {
      scanf("%d%d%d%d", &q, &l, &r, &d);
      for (int j = l; j <= r; j++) b[j] = (b[j] + d) % 998244353;
    }
    for (int i = (1), LIM = (n); i <= LIM; i++) b[i] = (q - b[i]) % 998244353;
    Sol(1, 1, n);
    printf("%d\n", (f[1][K] + 998244353) % 998244353);
  }
}