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;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
namespace {
const int mo = 998244353;
inline int add(int x, int y) {
  x += y;
  return x >= mo ? x - mo : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mo : x;
}
inline int mul(int x, int y) { return (long long)x * y % mo; }
inline int power(int a, int k = mo - 2) {
  int ans = 1;
  for (; k; k >>= 1, a = mul(a, a))
    if (k & 1) ans = mul(ans, a);
  return ans;
}
}  // namespace
namespace FFT {
const int N = 3e6 + 233;
const int G = 3;
int fft_l, fft_n, rev[N];
unsigned long long wn[N << 1], *data[30];
inline void prepare(int n) {
  fft_l = -1;
  fft_n = 1;
  while (fft_n < n) fft_n <<= 1, ++fft_l;
  for (int i = 1; i < fft_n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << fft_l);
  unsigned long long *cur = wn;
  for (int cn = 2, k = 0; cn <= fft_n; cn <<= 1, ++k) {
    data[k] = cur;
    unsigned long long t = power(G, (mo - 1) / cn), w = 1;
    for (register int k = 0; k < (int)cn; k++) *cur++ = w, w = w * t % mo;
  }
}
inline void dft(unsigned long long *a, int n) {
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int m = 1, step = 0; m < n; m <<= 1, ++step) {
    for (int i = 0; i < n; i += m << 1) {
      unsigned long long *l = a + i, *r = a + i + m, *w = data[step];
      for (int k = 0; k < m; k++) {
        unsigned long long y = *r * *w % mo;
        *r = *l + mo - y;
        *l += y;
        ++l;
        ++r;
        ++w;
      }
    }
  }
  for (int i = 0; i < n; i++) a[i] %= mo;
}
inline void idft(unsigned long long *a, int n) {
  dft(a, n);
  reverse(a + 1, a + n);
  unsigned long long invn = power(n);
  for (int i = 0; i < n; i++) a[i] = a[i] * invn % mo;
}
vector<int> realmain(vector<int> a, vector<int> b) {
  static unsigned long long x[N], y[N];
  int n = a.size(), m = b.size();
  prepare(n + m - 1);
  for (int i = 0; i < fft_n; i++) {
    x[i] = i < n ? a[i] : 0;
    y[i] = i < m ? b[i] : 0;
  }
  dft(x, fft_n);
  dft(y, fft_n);
  for (int i = 0; i < fft_n; i++) {
    x[i] = mul(x[i], y[i]);
  }
  idft(x, fft_n);
  return vector<int>(x, x + n + m - 1);
}
}  // namespace FFT
const int N = 3e4 + 233;
int n, K, b[N], q, a[N];
vector<int> solve(int l, int r) {
  if (l == r) return {1, a[l]};
  int mid = l + (r - l) / 2;
  return FFT::realmain(solve(l, mid), solve(mid + 1, r));
}
int main(void) {
  read(n);
  read(K);
  for (register int i = 1; i <= (n); i++) read(b[i]);
  read(q);
  while (q--) {
    int tp, q, i, d, l, r;
    read(tp);
    read(q);
    for (register int i = 1; i <= (n); i++) a[i] = b[i];
    if (tp == 1) {
      read(i);
      read(d);
      a[i] = d;
    } else {
      read(l);
      read(r);
      read(d);
      for (register int i = l; i <= r; i++) a[i] = add(a[i], d);
    }
    for (register int i = 1; i <= (n); i++) a[i] = sub(q, a[i]);
    vector<int> ans = solve(1, n);
    cout << ans[K] << "\n";
  }
}
