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;
namespace Flandre_Scarlet {
long long I() {
  char c = getchar();
  long long x = 0;
  long long f = 1;
  while (c < '0' or c > '9') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' and c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return ((f == 1) ? x : -x);
}
template <typename T>
void Rd(T& arg) {
  arg = I();
}
template <typename T, typename... Types>
void Rd(T& arg, Types&... args) {
  arg = I();
  Rd(args...);
}
void RA(long long* p, long long n) {
  for (long long i = 1; i <= n; ++i) *p = I(), ++p;
}
long long n, k, a[400005];
long long real_n;
void Input() {
  Rd(n, k);
  real_n = n;
  for (long long i = 1; i <= n; ++i) a[i] = I();
  long long nn = 1;
  while (nn < n) nn <<= 1;
  for (long long i = n + 1; i <= nn; ++i) a[i] = 0;
  n = nn;
}
long long qpow(long long a, long long b, long long m = 998244353) {
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % m;
    a = a * a % m, b >>= 1;
  }
  return r;
}
namespace K_Product {
long long rv[400005];
void NTT(long long A[], long long lim, long long type) {
  for (long long i = 0; i <= lim - 1; ++i)
    if (i < rv[i]) swap(A[i], A[rv[i]]);
  long long w[400005];
  w[0] = 1;
  for (long long mid = 1; mid < lim; mid <<= 1) {
    long long Wn =
        qpow(type == 1 ? 3 : 332748118, (998244353 - 1) / (mid << 1));
    for (long long i = 1; i <= mid - 1; ++i) w[i] = w[i - 1] * Wn % 998244353;
    for (long long i = 0; i < lim; i += (mid << 1))
      for (long long j = 0; j <= mid - 1; ++j) {
        long long t = w[j] * A[i | mid | j] % 998244353;
        A[i | mid | j] = (A[i | j] + 998244353 - t) % 998244353;
        A[i | j] = (A[i | j] + t) % 998244353;
      }
  }
  if (type == -1) {
    long long iv = qpow(lim, 998244353 - 2);
    for (long long i = 0; i <= lim - 1; ++i) A[i] = A[i] * iv % 998244353;
  }
}
long long pool[400005 << 2], *p[400005 << 2], *cur;
long long len[400005 << 2];
long long A[400005], B[400005];
void calc(long long l, long long r, long long ix = 1) {
  p[ix] = cur;
  if (l == r) {
    p[ix][0] = 1;
    p[ix][1] = a[l];
    len[ix] = 1;
    cur += 2;
    return;
  }
  long long mid = (l + r) >> 1;
  calc(l, mid, (ix << 1));
  calc(mid + 1, r, (ix << 1 | 1));
  len[ix] = len[(ix << 1)] + len[(ix << 1 | 1)];
  long long lim = len[ix] << 1;
  for (long long i = 0; i <= lim - 1; ++i)
    rv[i] = ((rv[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0));
  ;
  for (long long i = 0; i <= lim - 1; ++i) A[i] = B[i] = 0;
  for (long long i = 0; i <= len[(ix << 1)]; ++i)
    A[i] = p[(ix << 1)][i], B[i] = p[(ix << 1 | 1)][i];
  NTT(A, lim, 1);
  NTT(B, lim, 1);
  for (long long i = 0; i <= lim - 1; ++i) p[ix][i] = A[i] * B[i] % 998244353;
  NTT(p[ix], lim, -1);
  cur += lim;
}
void Main() {
  for (long long i = real_n + 1; i <= n; ++i) a[i] = 0;
  for (long long i = 1; i <= n; ++i)
    a[i] = (a[i] % 998244353 + 998244353) % 998244353;
  memset(pool, 0, sizeof(pool));
  cur = pool;
  calc(1, n);
  printf("%lld\n", p[1][k]);
}
}  // namespace K_Product
long long tmp[400005];
void Soviet() {
  long long q = I();
  for (long long tt = 1; tt <= q; ++tt) {
    for (long long i = 1; i <= n; ++i) tmp[i] = a[i];
    long long type = I();
    if (type == 1) {
      long long q, p, d;
      Rd(q, p, d);
      a[p] = d;
      for (long long i = 1; i <= n; ++i) a[i] = q - a[i];
    }
    if (type == 2) {
      long long q, l, r, d;
      Rd(q, l, r, d);
      for (long long i = l; i <= r; ++i) a[i] += d;
      for (long long i = 1; i <= n; ++i) a[i] = q - a[i];
    }
    K_Product::Main();
    for (long long i = 1; i <= n; ++i) a[i] = tmp[i];
  }
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  return 0;
}