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 TH>
void _dbg(const char* sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t) {
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
  bool operator<(const Triple& t) const {
    if (first != t.first) return first < t.first;
    if (second != t.second) return second < t.second;
    return third < t.third;
  }
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
template <class A, class B, class C>
ostream& operator<<(ostream& out, Triple<A, B, C> t) {
  return out << "(" << t.first << ", " << t.second << ", " << t.third << ")";
}
template <class T>
ostream& operator<<(ostream& out, vector<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
template <class T>
ostream& operator<<(ostream& out, set<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
template <class L, class R>
ostream& operator<<(ostream& out, map<L, R> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
const long long mod = 998244353;
const long long p = mod;
const long long gen = 5;
long long powMod(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) {
      res = ((long long)res * a) % p;
    }
    n >>= 1;
    a = ((long long)a * a) % p;
  }
  return res;
}
struct FFT {
 private:
  long long *A, *B, *tmp, *res, *omega;
  long long* perm;
  long long maxh;
  void Clear(long long n) {
    for (long long i = 0; i < (n); ++i) {
      A[i] = B[i] = res[i] = tmp[i] = 0;
    }
  }
  void fft(long long* from, long long* to, long long depth, bool inv) {
    long long N = (1 << depth);
    for (long long i = 0; i < N; i++) {
      to[perm[i] >> (maxh - depth)] = from[i];
    }
    for (long long m = (1); m <= (depth); ++m) {
      long long step = 1 << m;
      for (long long pos = 0; pos < N; pos += step) {
        long long cur = 0;
        long long delta = 1 << (maxh - m);
        if (!inv) {
          cur = 1 << maxh;
          delta *= -1;
        }
        long long *lft = to + pos, *rgt = lft + step / 2;
        for (long long k = 0; k < (step / 2); ++k) {
          long long a = *lft, b = (long long)omega[cur] * *rgt % mod;
          *lft = a + b;
          if (*lft >= mod) {
            *lft -= mod;
          }
          ++lft;
          *rgt = a - b;
          if (*rgt < 0) {
            *rgt += mod;
          }
          ++rgt;
          cur += delta;
        }
      }
    }
    if (inv) {
      const long long a = powMod(N, mod - 2);
      for (long long i = 0; i < (N); ++i) {
        to[i] = (long long)to[i] * a % mod;
      }
    }
  }

 public:
  FFT(long long deg) {
    maxh = 0;
    long long N = 1, h = -1;
    while (N <= 2 * deg) {
      maxh++;
      N *= 2;
    }
    deg = N + 20;
    A = new long long[deg];
    B = new long long[deg];
    res = new long long[deg];
    tmp = new long long[deg];
    omega = new long long[deg];
    perm = new long long[deg];
    omega[0] = 1;
    omega[1] = powMod(gen, (p - 1) / N);
    for (long long i = 2; i <= N; ++i) {
      omega[i] = (long long)omega[i - 1] * omega[1] % mod;
    }
    perm[0] = 0;
    for (long long i = (1); i <= (N - 1); ++i) {
      if ((i & (i - 1)) == 0) {
        h++;
      }
      perm[i] = perm[i ^ (1 << h)] | (1 << (maxh - h - 1));
    }
  }
  vector<long long> mul(vector<long long> Q, vector<long long> R) {
    long long depth = 0, size = 1;
    long long N = ((long long)(Q).size()) + ((long long)(R).size()) - 1;
    while (size < N) {
      depth++;
      size *= 2;
    }
    Clear(size);
    copy((Q).begin(), (Q).end(), A);
    copy((R).begin(), (R).end(), B);
    fft(A, res, depth, false);
    if (Q == R) {
      for (long long i = 0; i < (size); ++i)
        tmp[i] = (long long)res[i] * res[i] % mod;
    } else {
      fft(B, tmp, depth, false);
      for (long long i = 0; i < (size); ++i)
        tmp[i] = (long long)tmp[i] * res[i] % mod;
    }
    fft(tmp, res, depth, true);
    vector<long long> ans;
    for (long long i = 0; i < (N); ++i) {
      ans.push_back(res[i]);
    }
    return ans;
  }
};
FFT fft((long long)2e4 + 5);
vector<long long> Rec(vector<long long>& B, long long L, long long R,
                      long long k) {
  if (L == R) {
    return {1, B[L]};
  }
  long long M = (L + R) / 2;
  vector<long long> lewo = Rec(B, L, M, k);
  vector<long long> prawo = Rec(B, M + 1, R, k);
  vector<long long> res = fft.mul(lewo, prawo);
  if (((long long)(res).size()) > k + 1) {
    res.resize(k + 1);
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  if (0) cout << fixed << setprecision(10);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n);
  for (long long i = 0; i < (n); ++i) {
    cin >> a[i];
  }
  long long q;
  cin >> q;
  for (long long qq = (1); qq <= (q); ++qq) {
    long long t, x;
    cin >> t >> x;
    vector<long long> B;
    if (t == 1) {
      long long i, d;
      cin >> i >> d;
      B = a;
      B[i - 1] = d;
    } else {
      long long L, R, d;
      cin >> L >> R >> d;
      L--;
      R--;
      B = a;
      for (long long i = (L); i <= (R); ++i) {
        B[i] += d;
      }
    }
    for (long long i = 0; i < (((long long)(B).size())); ++i) {
      B[i] = x - B[i];
      B[i] = (B[i] % mod + mod) % mod;
    }
    cout << Rec(B, 0, ((long long)(B).size()) - 1, k)[k] << "\n";
  }
  return 0;
}