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;
const int MAXN = 33333;
const int mod = 998244353, G = 3;
int n, k, T, a[MAXN], W, rev[MAXN], gen[MAXN];
vector<int> vec[MAXN];
inline int qpow(int a, int b) {
  int re = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) re = 1ll * re * a % mod;
  return re;
}
inline int pls(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline void add(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
void NTT(vector<int> &arr, int len, int flg) {
  for (int i = 0; i < len; ++i)
    if (i < rev[i]) swap(arr[i], arr[rev[i]]);
  for (int v, i = 2, B = W >> 1; i <= len; i <<= 1, B >>= 1)
    for (int j = 0; j < len; j += i)
      for (int k = j, x = 0; k < j + i / 2; ++k, x += B)
        arr[k + i / 2] = pls(
            arr[k],
            mod - (v = 1ll * arr[k + i / 2] * gen[flg == 1 ? x : W - x] % mod)),
                    add(arr[k], v);
  if (flg == -1) {
    int iv = qpow(len, mod - 2);
    for (int i = 0; i < len; ++i) arr[i] = 1ll * arr[i] * iv % mod;
  }
}
vector<int> solve(int l, int r) {
  if (l == r) return vec[l];
  int mid = (l + r) >> 1;
  vector<int> L = solve(l, mid), R = solve(mid + 1, r);
  int len = 1;
  while (len <= r - l + 1) len <<= 1;
  for (int i = 1; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
  L.resize(len), R.resize(len);
  NTT(L, len, 1), NTT(R, len, 1);
  for (int i = 0; i < len; ++i) L[i] = 1ll * L[i] * R[i] % mod;
  NTT(L, len, -1);
  L.resize(r - l + 2);
  return L;
}
int main() {
  scanf("%d%d", &n, &k);
  for (W = 1; W <= n; W <<= 1)
    ;
  gen[0] = 1, gen[1] = qpow(G, (mod - 1) / W);
  for (int i = 2; i <= W; ++i) gen[i] = 1ll * gen[i - 1] * gen[1] % mod;
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]), vec[i].resize(2), vec[i][0] = 1;
  int op, q, x, y, d;
  for (scanf("%d", &T); T--;) {
    scanf("%d%d%d", &op, &q, &x);
    if (op == 2)
      scanf("%d", &y);
    else
      y = x;
    scanf("%d", &d);
    for (int i = 1; i <= n; ++i)
      vec[i][1] =
          ((q - ((x <= i && i <= y) ? (op == 1 ? d : a[i] + d) : a[i])) % mod +
           mod) %
          mod;
    vector<int> ans = solve(1, n);
    printf("%d\n", ans[k]);
  }
}