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>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
const long long MOD = 998244353;
const long long me = 22;
const long long ms = 1 << me;
long long fexp(long long x, long long e, long long mod = MOD) {
  long long ans = 1;
  x %= mod;
  for (; e > 0; e /= 2) {
    if (e & 1) {
      ans = ans * x % mod;
    }
    x = x * x % mod;
  }
  return ans;
}
bool test(long long x, long long p) {
  long long m = p - 1;
  for (long long i = 2; i * i <= m; ++i)
    if (!(m % i)) {
      if (fexp(x, i, p) == 1) return false;
      if (fexp(x, m / i, p) == 1) return false;
    }
  return true;
}
long long search(long long p) {
  for (long long i = p - 1; i >= 2; --i)
    if (test(i, p)) return i;
  return -1;
}
std::map<long long, long long> roots;
long long get_root(long long p) {
  if (roots[p]) {
    return roots[p];
  } else {
    roots[p] = search(p);
    return roots[p];
  }
}
const long long gen = search(MOD);
long long bits[ms], root[ms];
void initFFT() {
  root[1] = 1;
  for (long long len = 2; len < ms; len += len) {
    long long z = fexp(gen, (MOD - 1) / len / 2);
    for (long long i = len / 2; i < len; i++) {
      root[2 * i] = root[i];
      root[2 * i + 1] = (long long)root[i] * z % MOD;
    }
  }
}
void pre(long long n) {
  long long LOG = 0;
  while (1 << (LOG + 1) < n) {
    LOG++;
  }
  for (long long i = 1; i < n; i++) {
    bits[i] = (bits[i >> 1] >> 1) | ((i & 1) << LOG);
  }
}
std::vector<long long> fft(std::vector<long long> a, bool inv = false) {
  long long n = (long long)a.size();
  pre(n);
  if (inv) {
    std::reverse(a.begin() + 1, a.end());
  }
  for (long long i = 0; i < n; i++) {
    long long to = bits[i];
    if (i < to) {
      std::swap(a[i], a[to]);
    }
  }
  for (long long len = 1; len < n; len *= 2) {
    for (long long i = 0; i < n; i += len * 2) {
      for (long long j = 0; j < len; j++) {
        long long u = a[i + j],
                  v = (long long)a[i + j + len] * root[len + j] % MOD;
        a[i + j] = (u + v) % MOD;
        a[i + j + len] = (u - v) % MOD;
      }
    }
  }
  if (inv) {
    long long rev = fexp(n, MOD - 2);
    for (long long i = 0; i < n; i++) a[i] = (long long)a[i] * rev % MOD;
  }
  return a;
}
std::vector<long long> mul(std::vector<long long> a, std::vector<long long> b) {
  long long n = 1;
  while (n < a.size() + b.size()) n += n;
  a.resize(n, 0);
  b.resize(n, 0);
  a = fft(a);
  b = fft(b);
  for (long long i = 0; i < n; i++) {
    a[i] = (long long)a[i] * b[i] % MOD;
  }
  a = fft(a, true);
  while (!a.empty() && a.back() == 0) {
    a.pop_back();
  }
  return a;
}
struct Comp {
  bool operator()(const std::vector<long long> &a,
                  const std::vector<long long> &b) {
    return a.size() > b.size();
  }
};
std::vector<long long> solve(const std::vector<long long> &coef) {
  std::priority_queue<std::vector<long long>,
                      std::vector<std::vector<long long>>, Comp>
      hp;
  for (long long i = 0; i < (long long)coef.size(); i++) {
    std::vector<long long> cur(2);
    cur[0] = 1;
    cur[1] = (coef[i] % MOD + MOD) % MOD;
    hp.push(cur);
  }
  while (hp.size() > 1) {
    auto a = hp.top();
    hp.pop();
    a = mul(a, hp.top());
    hp.pop();
    hp.push(a);
  }
  auto ans = hp.top();
  ans.resize(100100, 0);
  return ans;
}
int32_t main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  initFFT();
  long long n, k;
  std::cin >> n >> k;
  std::vector<long long> a(n);
  for (long long i = 0; i < n; i++) {
    std::cin >> a[i];
    a[i] %= MOD;
  }
  long long q;
  std::cin >> q;
  while (q--) {
    long long t;
    std::cin >> t;
    std::vector<long long> b(n);
    if (t == 1) {
      long long q, pos, d;
      std::cin >> q >> pos >> d;
      pos--;
      for (long long i = 0; i < n; i++) {
        long long x = a[i];
        if (i == pos) {
          x = d;
        }
        b[i] = (q - x + MOD) % MOD;
      }
    } else {
      long long q, l, r, d;
      std::cin >> q >> l >> r >> d;
      l--;
      for (long long i = 0; i < n; i++) {
        long long x = a[i];
        if (l <= i && i < r) {
          x = (x + d) % MOD;
        }
        b[i] = (q - x + MOD) % MOD;
      }
    }
    std::cout << (solve(b)[k] % MOD + MOD) % MOD << '\n';
  }
}
