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>
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline void sub(long long &a, long long b) {
  a -= b;
  if (a < 0) a += 998244353;
}
inline void add(long long &a, long long b) {
  a += b;
  if (a >= 998244353) a -= 998244353;
}
template <typename T>
inline T const &MAX(T const &a, T const &b) {
  return a > b ? a : b;
}
template <typename T>
inline T const &MIN(T const &a, T const &b) {
  return a < b ? a : b;
}
inline long long mul(long long a, long long b, long long c) {
  return (a * b - (long long)((long double)a * b / c) * c + c) % c;
}
inline long long qp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 998244353;
    a = a * a % 998244353, b >>= 1;
  }
  return ans;
}
inline long long qp(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a, c);
    a = mul(a, a, c), b >>= 1;
  }
  return ans;
}
using namespace std;
const long double pi = acos(-1);
const unsigned long long ba = 233;
const double eps = 1e-5;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 200000 + 10, maxn = 2000000 + 10, inf = 0x3f3f3f3f;
long long x[N << 3], y[N << 3];
int rev[N << 3];
void getrev(int bit) {
  for (int i = 0; i < (1 << bit); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
void ntt(long long *a, int n, int dft) {
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int step = 1; step < n; step <<= 1) {
    long long wn = qp(3, (998244353 - 1) / (step * 2));
    if (dft == -1) wn = qp(wn, 998244353 - 2);
    for (int j = 0; j < n; j += step << 1) {
      long long wnk = 1;
      for (int k = j; k < j + step; k++) {
        long long x = a[k];
        long long y = wnk * a[k + step] % 998244353;
        a[k] = (x + y) % 998244353;
        a[k + step] = (x - y + 998244353) % 998244353;
        wnk = wnk * wn % 998244353;
      }
    }
  }
  if (dft == -1) {
    long long inv = qp(n, 998244353 - 2);
    for (int i = 0; i < n; i++) a[i] = a[i] * inv % 998244353;
  }
}
vector<int> v[N << 2];
int a[N], b[N];
void solve(int l, int r, int rt) {
  if (l == r) {
    v[rt].clear();
    v[rt].push_back(1);
    v[rt].push_back(b[l]);
    return;
  }
  int m = (l + r) >> 1;
  solve(l, m, rt << 1);
  solve(m + 1, r, rt << 1 | 1);
  int p = v[rt << 1].size(), q = v[rt << 1 | 1].size();
  int sz = 0;
  while ((1 << sz) <= p + q) sz++;
  getrev(sz);
  int len = (1 << sz);
  for (int i = 0; i < len; i++) {
    x[i] = (i < p ? v[rt << 1][i] : 0);
    y[i] = (i < q ? v[rt << 1 | 1][i] : 0);
  }
  ntt(x, len, 1);
  ntt(y, len, 1);
  for (int i = 0; i < len; i++) x[i] = x[i] * y[i] % 998244353;
  ntt(x, len, -1);
  v[rt].clear();
  for (int i = 0; i < len; i++) v[rt].push_back(x[i]);
  while (v[rt].size() && v[rt].back() == 0) v[rt].pop_back();
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] %= 998244353;
  int q;
  scanf("%d", &q);
  while (q--) {
    int op, q, x, y, z;
    scanf("%d%d%d%d", &op, &q, &x, &y);
    if (op == 1) {
      q %= 998244353, y %= 998244353;
      for (int i = 1; i <= n; i++) {
        b[i] = (i == x ? q - y : q - a[i]);
        if (b[i] < 0) b[i] += 998244353;
      }
    } else {
      scanf("%d", &z);
      q %= 998244353, z %= 998244353;
      for (int i = 1; i <= n; i++) {
        if (x <= i && i <= y)
          b[i] = ((q - a[i] - z) % 998244353 + 998244353) % 998244353;
        else
          b[i] = (q - a[i] + 998244353) % 998244353;
      }
    }
    solve(1, n, 1);
    printf("%d\n", v[1][k]);
  }
  return 0;
}