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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 1e6 + 10, P = 998244353, G = 3, Gi = 332748118;
int N, r[MAXN];
long long a[MAXN];
long long K, Q;
vector<vector<long long> > mp;
long long fastpow(long long a, long long k) {
  long long base = 1;
  while (k) {
    if (k & 1) base = (base * a) % P;
    a = (a * a) % P;
    k >>= 1;
  }
  return base % P;
}
long long b[MAXN];
void NTT(vector<long long> &A, long long type, long long limit) {
  for (long long i = 0; i < limit; i++)
    if (i < r[i]) A[i] ^= A[r[i]], A[r[i]] ^= A[i], A[i] ^= A[r[i]];
  for (long long mid = 1; mid < limit; mid <<= 1) {
    long long Wn = fastpow(type == 1 ? G : Gi, (P - 1) / (mid << 1));
    for (long long j = 0; j < limit; j += (mid << 1)) {
      long long w = 1;
      for (long long k = 0; k < mid; k++, w = (w * Wn) % P) {
        long long x = A[j + k], y = w * A[j + k + mid] % P;
        A[j + k] = (x + y) % P, A[j + k + mid] = (x - y + P) % P;
      }
    }
  }
}
vector<long long> conv(vector<long long> &a, long long N, vector<long long> &b,
                       long long M, long long limit, long long L) {
  vector<long long> c(limit + 1);
  for (long long i = 0; i < limit; i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
  NTT(a, 1, limit);
  NTT(b, 1, limit);
  for (long long i = 0; i < limit; i++) c[i] = (a[i] * b[i]) % P;
  NTT(c, -1, limit);
  long long inv = fastpow(limit, P - 2);
  for (long long i = 0; i <= limit; i++) c[i] = c[i] * inv % P;
  return c;
}
vector<long long> divide(long long l, long long r) {
  if (l == r) {
    vector<long long> res(2);
    res[0] = 1;
    res[1] = b[l];
    return res;
  }
  long long mid = (l + r) >> 1;
  vector<long long> LL = divide(l, mid), RR = divide(mid + 1, r);
  long long limit = 1;
  long long L = 0;
  while (limit <= 2 * (r - l + 1)) limit <<= 1, L++;
  while (LL.size() < limit) LL.push_back(0);
  while (RR.size() < limit) RR.push_back(0);
  auto c = conv(LL, LL.size(), RR, RR.size(), limit, L);
  LL.clear();
  RR.clear();
  return c;
}
int main() {
  scanf("%lld%lld", &N, &K);
  for (long long i = 1; i <= N; i++) scanf("%lld", &a[i]);
  scanf("%lld", &Q);
  while (Q--) {
    long long op;
    scanf("%lld", &op);
    mp.clear();
    mp.resize(N + 1);
    if (op == 1) {
      long long q, d;
      long long ii;
      scanf("%lld%lld%lld", &q, &ii, &d);
      for (long long i = 1; i <= N; i++) {
        if (i == ii)
          b[i] = (q - d + P) % P;
        else
          b[i] = (q - a[i] + P) % P;
      }
    } else {
      long long q, d;
      long long LL, RR;
      scanf("%lld%lld%lld%lld", &q, &LL, &RR, &d);
      for (long long i = 1; i <= N; i++) {
        if (i >= LL && i <= RR)
          b[i] = (q - a[i] - d + P) % P;
        else
          b[i] = (q - a[i] + P) % P;
      }
    }
    vector<long long> res = divide(1, N);
    printf("%lld\n", res[K] % P);
  }
  return 0;
}
