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;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  os << '{';
  string sep;
  for (const auto &x : arr) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
template <class T>
bool cmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool cmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const long long MOD = 998244353;
long long mod_pow(long long a, long long b, long long mod = MOD) {
  long long ret = 1;
  a %= mod;
  while (b > 0) {
    if (b % 2) ret = ret * a % mod;
    b /= 2;
    a = a * a % mod;
  }
  return ret;
}
long long mod_mul(long long a, long long b) { return a * b % MOD; }
long long mod_sub(long long a, long long b) { return (a - b + MOD) % MOD; }
long long mod_add(long long a, long long b) { return (a + b) % MOD; }
long long mod_inv(long long a) { return mod_pow(a, MOD - 2, MOD); }
namespace NTT {
vector<long long> roots = {0, 1};
vector<long long> bit_reverse;
long long max_size = -1;
long long root;
bool is_power_of_two(long long n) { return (n & (n - 1)) == 0; }
long long round_up_power_two(long long n) {
  assert(n > 0);
  while (n & (n - 1)) n = (n | (n - 1)) + 1;
  return n;
}
long long get_length(long long n) {
  assert(is_power_of_two(n));
  return __builtin_ctz(n);
}
void bit_reorder(long long n, vector<long long> &values) {
  if ((long long)bit_reverse.size() != n) {
    bit_reverse.assign(n, 0);
    long long length = get_length(n);
    for (long long i = 0; i < n; i++)
      bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
  }
  for (long long i = 0; i < n; i++)
    if (i < bit_reverse[i]) swap(values[i], values[bit_reverse[i]]);
}
void find_root() {
  long long order = MOD - 1;
  max_size = 1;
  while (order % 2 == 0) {
    order /= 2;
    max_size *= 2;
  }
  root = 2;
  while (!(mod_pow(root, max_size) == 1 && mod_pow(root, max_size / 2) != 1))
    root++;
}
void prepare_roots(long long n) {
  if (max_size < 0) find_root();
  if ((long long)roots.size() >= n) return;
  long long length = get_length(roots.size());
  roots.resize(n);
  while (1 << length < n) {
    long long z = mod_pow(root, max_size >> (length + 1));
    for (long long i = 1 << (length - 1); i < 1 << length; i++) {
      roots[2 * i] = roots[i];
      roots[2 * i + 1] = mod_mul(roots[i], z);
    }
    length++;
  }
}
void fft_iterative(long long N, vector<long long> &values) {
  assert(is_power_of_two(N));
  prepare_roots(N);
  bit_reorder(N, values);
  assert(N <= max_size);
  for (long long n = 1; n < N; n *= 2)
    for (long long start = 0; start < N; start += 2 * n)
      for (long long i = 0; i < n; i++) {
        long long even = values[start + i];
        long long odd = mod_mul(values[start + n + i], roots[n + i]);
        values[start + n + i] = mod_sub(even, odd);
        values[start + i] = mod_add(even, odd);
      }
}
const long long FFT_CUTOFF = 150;
vector<long long> mod_multiply(vector<long long> left, vector<long long> right,
                               bool trim = true) {
  long long n = left.size();
  long long m = right.size();
  for (long long i = 0; i < n; i++) assert(0 <= left[i] && left[i] < MOD);
  for (long long i = 0; i < m; i++) assert(0 <= right[i] && right[i] < MOD);
  if (min(n, m) < FFT_CUTOFF) {
    const uint64_t ULL_BOUND =
        numeric_limits<uint64_t>::max() - (uint64_t)MOD * MOD;
    vector<uint64_t> result(n + m - 1);
    for (long long i = 0; i < n; i++)
      for (long long j = 0; j < m; j++) {
        result[i + j] += (uint64_t)left[i] * right[j];
        if (result[i + j] > ULL_BOUND) result[i + j] %= MOD;
      }
    for (long long i = 0; i < (long long)result.size(); i++)
      if (result[i] >= (uint64_t)MOD) result[i] %= MOD;
    if (trim) {
      while (!result.empty() && result.back() == 0) result.pop_back();
    }
    return vector<long long>(result.begin(), result.end());
  }
  long long N = round_up_power_two(n + m - 1);
  left.resize(N);
  right.resize(N);
  bool equal = left == right;
  fft_iterative(N, left);
  if (equal)
    right = left;
  else
    fft_iterative(N, right);
  long long inv_N = mod_inv(N);
  for (long long i = 0; i < N; i++)
    left[i] = mod_mul(mod_mul(left[i], right[i]), inv_N);
  reverse(left.begin() + 1, left.end());
  fft_iterative(N, left);
  left.resize(n + m - 1);
  if (trim) {
    while (!left.empty() && left.back() == 0) left.pop_back();
  }
  return left;
}
vector<long long> power(const vector<long long> &v, long long exponent) {
  assert(exponent >= 0);
  vector<long long> result = {1};
  if (exponent == 0) return result;
  for (long long k = 31 - __builtin_clz(exponent); k >= 0; k--) {
    result = mod_multiply(result, result);
    if (exponent & 1 << k) result = mod_multiply(result, v);
  }
  return result;
}
};  // namespace NTT
const long long N = 2e4 + 5;
long long n, k, a[N], b[N], Q, type, q, L, R, d;
vector<long long> divide_conquer(long long L, long long R) {
  if (L == R) return {1, b[L]};
  long long mid = (L + R) >> 1;
  return NTT::mod_multiply(divide_conquer(L, mid), divide_conquer(mid + 1, R));
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (long long i = (1); i <= (n); i++) {
    cin >> a[i];
    a[i] %= MOD;
  }
  cin >> Q;
  while (Q--) {
    for (long long i = (1); i <= (n); i++) b[i] = a[i];
    cin >> type >> q;
    if (type == 1) {
      long long id, val;
      cin >> id >> val;
      b[id] = val % MOD;
    } else {
      cin >> L >> R >> d;
      for (long long i = (L); i <= (R); i++) b[i] = (b[i] + d) % MOD;
    }
    for (long long i = (1); i <= (n); i++) b[i] = (q - b[i] + MOD) % MOD;
    vector<long long> all_answers = divide_conquer(1, n);
    ;
    cout << (k < (long long)(all_answers.size()) ? all_answers[k] : 0) << '\n';
  }
}