#include <bits/stdc++.h>
using namespace std;
const int P = 998244353, R = 3;
int mpow(int x, int k, int p = P) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = ret * (long long)x % p;
    x = x * (long long)x % p;
    k >>= 1;
  }
  return ret;
}
int norm(int x) { return x >= P ? (x - P) : x; }
struct NumberTheory {
  mt19937 rng;
  NumberTheory()
      : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
  void _exGcd(int a, int b, int& x, int& y) {
    if (!b) {
      x = 1;
      y = 0;
      return;
    }
    _exGcd(b, a % b, y, x);
    y -= a / b * x;
  }
  int inv(int a, int p = P) {
    int x, y;
    _exGcd(a, p, x, y);
    if (x < 0) x += p;
    return x;
  }
  template <class Integer>
  bool quadRes(Integer a, Integer b) {
    if (a <= 1) return true;
    while (a % 4 == 0) a /= 4;
    if (a % 2 == 0) return (b % 8 == 1 || b % 8 == 7) == quadRes(a / 2, b);
    return ((a - 1) % 4 == 0 || (b - 1) % 4 == 0) == quadRes(b % a, a);
  }
  int sqrt(int x, int p = P) {
    if (p == 2 || x <= 1) return x;
    int w, v, k = (p + 1) / 2;
    do {
      w = rng() % p;
    } while (quadRes(v = int((w * (long long)w - x + p) % p), p));
    pair<int, int> res(1, 0), a(w, 1);
    while (k) {
      if (k & 1)
        res = pair<int, int>((res.first * (long long)a.first +
                              res.second * (long long)a.second % p * v) %
                                 p,
                             (res.first * (long long)a.second +
                              res.second * (long long)a.first) %
                                 p);
      if (k >>= 1)
        a = pair<int, int>((a.first * (long long)a.first +
                            a.second * (long long)a.second % p * v) %
                               p,
                           (a.first * (long long)a.second << 1) % p);
    }
    return min(res.first, p - res.first);
  }
} nt;
template <class T, class Comp>
struct AdditionChain {
  int k;
  vector<T> prepare;
  T t, unit;
  Comp comp;
  AdditionChain(const T& t, const Comp& comp, int k, const T& unit = 1)
      : comp(comp), t(t), unit(unit), k(k), prepare(1U << k) {
    prepare[0] = unit;
    for (int i = 1; i < 1 << k; ++i) prepare[i] = comp(prepare[i - 1], t);
  }
  static AdditionChain fourRussians(const T& t, const Comp& comp, int lgn,
                                    const T& unit = 1) {
    lgn = max(lgn, 1);
    int k = 1, lglgn = 1;
    while (2 << lglgn <= lgn) ++lglgn;
    int w = lglgn / lgn;
    while (1 << k < w) ++k;
    return AdditionChain(t, comp, k, unit);
  }
  T pow(int n) const {
    if (n < 1 << k) return prepare[n];
    int r = n & ((1 << k) - 1);
    T step = pow(n >> k);
    for (int rep = 0; rep < k; ++rep) step = comp(step, step);
    return comp(step, prepare[r]);
  }
};
struct Simple {
  int n;
  vector<int> fac, ifac, inv;
  void build(int n) {
    this->n = n;
    fac.resize(n + 1);
    ifac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = 1;
    for (int x = 1; x <= n; ++x) fac[x] = fac[x - 1] * (long long)x % P;
    inv[1] = 1;
    for (int x = 2; x <= n; ++x)
      inv[x] = -(P / x) * (long long)inv[P % x] % P + P;
    ifac[0] = 1;
    for (int x = 1; x <= n; ++x) ifac[x] = ifac[x - 1] * (long long)inv[x] % P;
  }
  Simple() { build(1); }
  void check(int k) {
    int nn = n;
    if (k > nn) {
      while (k > nn) nn <<= 1;
      build(nn);
    }
  }
  int gfac(int k) {
    check(k);
    return fac[k];
  }
  int gifac(int k) {
    check(k);
    return ifac[k];
  }
  int ginv(int k) {
    check(k);
    return inv[k];
  }
  int binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return gfac(n) * (long long)gifac(m) % P * gifac(n - m) % P;
  }
} simp;
const int L2 = 11;
struct NTT {
  int L;
  int brev[1 << L2];
  vector<int> root;
  NTT() : L(-1) {
    for (int i = 1; i < (1 << L2); ++i)
      brev[i] = brev[i >> 1] >> 1 | ((i & 1) << (L2 - 1));
  }
  void prepRoot(int l) {
    L = l;
    root.resize(1 << L);
    int n = 1 << L;
    int primitive = mpow(R, (P - 1) >> L);
    root[0] = 1;
    for (int i = 1; i < n; ++i)
      root[i] = root[i - 1] * (long long)primitive % P;
  }
  void fft(int* a, int lgn, int d = 1) {
    if (L < lgn) prepRoot(lgn);
    int n = 1 << lgn;
    for (int i = 0; i < n; ++i) {
      int rev = (brev[i >> L2] | (brev[i & ((1 << L2) - 1)] << L2)) >>
                ((L2 << 1) - lgn);
      if (i < rev) swap(a[i], a[rev]);
    }
    int rt = d == 1 ? R : nt.inv(R);
    for (int k = L - 1, t = 1; t < n; t <<= 1, --k) {
      for (int i = 0; i < n; i += t << 1) {
        int *p1 = a + i, *p2 = a + i + t;
        for (int j = 0; j < t; ++j) {
          int x = p2[j] * (long long)root[j << k] % P;
          p2[j] = norm(p1[j] + P - x);
          p1[j] = norm(p1[j] + x);
        }
      }
    }
    if (d == -1) {
      reverse(a + 1, a + n);
      int nv = mpow(n, P - 2);
      for (int i = 0; i < n; ++i) a[i] = a[i] * (long long)nv % P;
    }
  }
} ntt;
struct Poly {
  vector<int> a;
  Poly(int v = 0) : a(1) {
    if ((v %= P) < 0) v += P;
    a[0] = v;
  }
  Poly(const vector<int>& a) : a(a) {}
  Poly(initializer_list<int> init) : a(init) {}
  int operator[](int k) const { return k < a.size() ? a[k] : 0; }
  int& operator[](int k) {
    if (k >= a.size()) a.resize(k + 1);
    return a[k];
  }
  int deg() const { return a.size() - 1; }
  void redeg(int d) { a.resize(d + 1); }
  Poly monic() const;
  Poly sunic() const;
  Poly slice(int d) const {
    if (d < a.size()) return vector<int>(a.begin(), a.begin() + d + 1);
    vector<int> res(a);
    res.resize(d + 1);
    return res;
  }
  int* base() { return a.begin().base(); }
  const int* base() const { return a.begin().base(); }
  Poly println(FILE* fp) const {
    fprintf(fp, "%d", a[0]);
    for (int i = 1; i < a.size(); ++i) fprintf(fp, " %d", a[i]);
    fputc('\n', fp);
    return *this;
  }
  Poly operator+(const Poly& rhs) const {
    vector<int> res(max(a.size(), rhs.a.size()));
    for (int i = 0; i < res.size(); ++i)
      if ((res[i] = operator[](i) + rhs[i]) >= P) res[i] -= P;
    return res;
  }
  Poly operator-() const {
    Poly ret(a);
    for (int i = 0; i < a.size(); ++i)
      if (ret[i]) ret[i] = P - ret[i];
    return ret;
  }
  Poly operator-(const Poly& rhs) const { return operator+(-rhs); }
  Poly operator*(const Poly& rhs) const;
  Poly operator/(const Poly& rhs) const;
  Poly operator%(const Poly& rhs) const;
  Poly der() const;
  Poly integ() const;
  Poly inv() const;
  Poly sqrt() const;
  Poly ln() const;
  Poly exp() const;
  pair<Poly, Poly> sqrti() const;
  Poly quo(const Poly& rhs) const;
  pair<Poly, Poly> iquo(const Poly& rhs) const;
  pair<Poly, Poly> div(const Poly& rhs) const;
  Poly taylor(int k) const;
  Poly pow(int k) const;
  Poly exp(int k) const;
};
Poly zeroes(int deg) { return vector<int>(deg + 1); }
struct Newton {
  void inv(const Poly& f, const Poly& nttf, Poly& g, const Poly& nttg, int t) {
    int n = 1 << t;
    Poly prod = nttf;
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (long long)nttg[i] % P;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i) prod[i] = 0;
    ntt.fft(prod.base(), t + 1, 1);
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (long long)nttg[i] % P;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i) prod[i] = 0;
    g = g - prod;
  }
  void inv(const Poly& f, const Poly& nttf, Poly& g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
  void inv(const Poly& f, Poly& g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly nttf = f;
    nttf.redeg((2 << t) - 1);
    ntt.fft(nttf.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
  void sqrt(const Poly& f, Poly& g, Poly& nttg, Poly& h, int t) {
    for (int i = 0; i < (1 << t); ++i) nttg[i] = mpow(nttg[i], 2);
    ntt.fft(nttg.base(), t, -1);
    nttg = nttg - f;
    for (int i = 0; i < (1 << t); ++i)
      if ((nttg[i + (1 << t)] += nttg[i]) >= P) nttg[i + (1 << t)] -= P;
    memset(nttg.base(), 0, sizeof(int) << t);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly tmp = h;
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) tmp[i] = tmp[i] * (long long)nttg[i] % P;
    ntt.fft(tmp.base(), t + 1, -1);
    memset(tmp.base(), 0, sizeof(int) << t);
    g = g - tmp * nt.inv(2);
  }
  void exp(const Poly& f, Poly& g, Poly& nttg, Poly& h, int t) {
    Poly ntth(h);
    ntt.fft(ntth.base(), t, 1);
    Poly dg = g.der().slice((1 << t) - 1);
    ntt.fft(dg.base(), t, 1);
    Poly tmp = zeroes((1 << t) - 1);
    for (int i = 0; i < (1 << t); ++i) {
      tmp[i] = nttg[i << 1] * (long long)ntth[i] % P;
      dg[i] = dg[i] * (long long)ntth[i] % P;
    }
    ntt.fft(tmp.base(), t, -1);
    ntt.fft(dg.base(), t, -1);
    if (--tmp[0] < 0) tmp[0] = P - 1;
    dg.redeg((2 << t) - 1);
    Poly df0 = f.der().slice((1 << t) - 1);
    df0[(1 << t) - 1] = 0;
    for (int i = 0; i < (1 << t); ++i) {
      if ((dg[i | 1 << t] = dg[i] - df0[i]) < 0) dg[i | 1 << t] += P;
    }
    memcpy(dg.base(), df0.base(), sizeof(int) * ((1 << t) - 1));
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    df0.redeg((2 << t) - 1);
    ntt.fft(df0.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) df0[i] = df0[i] * (long long)tmp[i] % P;
    ntt.fft(df0.base(), t + 1, -1);
    memcpy(df0.base() + (1 << t), df0.base(), sizeof(int) << t);
    memset(df0.base(), 0, sizeof(int) << t);
    dg = (dg - df0).integ().slice((2 << t) - 1) - f;
    ntt.fft(dg.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) tmp[i] = dg[i] * (long long)nttg[i] % P;
    ntt.fft(tmp.base(), t + 1, -1);
    g.redeg((2 << t) - 1);
    for (int i = 1 << t; i < (2 << t); ++i)
      if (tmp[i]) g[i] = P - tmp[i];
  }
} nit;
struct EvaluationHelper {
  int _t, _lim;
  vector<int> _tmp, _res, _tmpy;
  vector<Poly> _h, _r;
  EvaluationHelper() {}
  void _solve(int l, int r) {
    if (l == r) {
      _h[_t] = Poly{(P - _tmp[l]) % P, 1};
      ++_t;
      return;
    }
    int p = _t++;
    int ls = _t, mid = (l + r) >> 1;
    _solve(l, mid);
    int rs = _t;
    _solve(mid + 1, r);
    if ((r - l + 1) <= _lim) _h[p] = _h[ls] * _h[rs];
  }
  void _solve2(int l, int r) {
    if ((r - l + 1) <= _lim) _r[_t] = _r[_t] % _h[_t];
    if (l == r) {
      _res[l] = _r[_t][0];
      ++_t;
      return;
    }
    int p = _t++, mid = (l + r) >> 1;
    _r[_t] = _r[p] % _h[_t];
    _solve2(l, mid);
    _r[_t] = _r[p] % _h[_t];
    _solve2(mid + 1, r);
  }
  void _divideConquer(int l, int r) {
    if (l == r) {
      _r[_t] = nt.inv(_res[l]) * (long long)_tmpy[l] % P;
      ++_t;
      return;
    }
    int p = _t++, mid = (l + r) >> 1;
    int ls = _t;
    _divideConquer(l, mid);
    int rs = _t;
    _divideConquer(mid + 1, r);
    _r[p] = _r[ls] * _h[rs] + _r[rs] * _h[ls];
  }
  vector<int> evaluate(const Poly& p, const vector<int>& x) {
    if (x.empty()) return vector<int>();
    int n = x.size();
    _lim = n;
    _tmp = x;
    _h.resize(n * 2 - 1);
    _r.resize(n * 2 - 1);
    _t = 0;
    _solve(0, n - 1);
    _res.resize(n);
    _t = 0;
    _r[0] = p;
    _solve2(0, n - 1);
    _tmp.clear();
    _h.clear();
    _r.clear();
    return _res;
  }
  Poly interpolate(const vector<pair<int, int> >& points) {
    int n = points.size();
    _tmp.resize(n);
    for (int i = 0; i < n; ++i) _tmp[i] = points[i].first;
    _lim = n;
    _h.resize(n * 2 - 1);
    _r.resize(n * 2 - 1);
    _t = 0;
    _solve(0, n - 1);
    _res.resize(n);
    _t = 0;
    _r[0] = _h[0].der();
    _solve2(0, n - 1);
    _tmp.clear();
    _tmpy.resize(n);
    for (int i = 0; i < n; ++i) _tmpy[i] = points[i].second;
    _t = 0;
    _divideConquer(0, n - 1);
    return _r[0];
  }
} eh;
Poly operator"" _z(unsigned long long a) { return {0, (int)a}; }
Poly operator+(int v, const Poly& rhs) { return Poly(v) + rhs; }
Poly Poly::operator*(const Poly& rhs) const {
  int n = deg(), m = rhs.deg();
  if (n <= 10 || m <= 10) {
    Poly ret = zeroes(n + m);
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
        ret[i + j] = (ret[i + j] + a[i] * (long long)rhs[j]) % P;
    return ret;
  }
  n += m;
  int l = 0;
  while ((1 << l) <= n) ++l;
  vector<int> res(1 << l), tmp(1 << l);
  memcpy(res.begin().base(), base(), a.size() * sizeof(int));
  ntt.fft(res.begin().base(), l, 1);
  memcpy(tmp.begin().base(), rhs.base(), rhs.a.size() * sizeof(int));
  ntt.fft(tmp.begin().base(), l, 1);
  for (int i = 0; i < (1 << l); ++i) res[i] = res[i] * (long long)tmp[i] % P;
  ntt.fft(res.begin().base(), l, -1);
  res.resize(n + 1);
  return res;
}
Poly Poly::inv() const {
  Poly g = nt.inv(a[0]);
  for (int t = 0; (1 << t) <= deg(); ++t) nit.inv(slice((2 << t) - 1), g, t);
  g.redeg(deg());
  return g;
}
Poly Poly::taylor(int k) const {
  int n = deg();
  Poly t = zeroes(n);
  simp.check(n);
  for (int i = 0; i <= n; ++i) t[n - i] = a[i] * (long long)simp.fac[i] % P;
  int pw = 1;
  Poly help = vector<int>(simp.ifac.begin(), simp.ifac.begin() + n + 1);
  for (int i = 0; i <= n; ++i) {
    help[i] = help[i] * (long long)pw % P;
    pw = pw * (long long)k % P;
  }
  t = t * help;
  for (int i = 0; i <= n; ++i) help[i] = t[n - i] * (long long)simp.ifac[i] % P;
  return help;
}
Poly Poly::pow(int k) const {
  if (k == 0) return 1;
  if (k == 1) return *this;
  int n = deg() * k;
  int lgn = 0;
  while ((1 << lgn) <= n) ++lgn;
  vector<int> val = a;
  val.resize(1 << lgn);
  ntt.fft(val.begin().base(), lgn, 1);
  for (int i = 0; i < (1 << lgn); ++i) val[i] = mpow(val[i], k);
  ntt.fft(val.begin().base(), lgn, -1);
  return val;
}
Poly Poly::der() const {
  if (deg() == 0) return 0;
  vector<int> res(deg());
  for (int i = 0; i < deg(); ++i) res[i] = a[i + 1] * (long long)(i + 1) % P;
  return res;
}
Poly Poly::integ() const {
  vector<int> res(deg() + 2);
  simp.check(deg() + 1);
  for (int i = 0; i <= deg(); ++i)
    res[i + 1] = a[i] * (long long)simp.inv[i + 1] % P;
  return res;
}
Poly Poly::quo(const Poly& rhs) const {
  if (rhs.deg() == 0) return a[0] * (long long)nt.inv(rhs[0]) % P;
  Poly g = nt.inv(rhs[0]);
  int t = 0, n;
  for (n = 1; (n << 1) <= rhs.deg(); ++t, n <<= 1)
    nit.inv(rhs.slice((n << 1) - 1), g, t);
  Poly nttg = g;
  nttg.redeg((n << 1) - 1);
  ntt.fft(nttg.base(), t + 1, 1);
  Poly eps1 = rhs.slice((n << 1) - 1);
  ntt.fft(eps1.base(), t + 1, 1);
  for (int i = 0; i < (n << 1); ++i) eps1[i] = eps1[i] * (long long)nttg[i] % P;
  ntt.fft(eps1.base(), t + 1, -1);
  memcpy(eps1.base(), eps1.base() + n, sizeof(int) << t);
  memset(eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(eps1.base(), t + 1, 1);
  Poly h0 = slice(n - 1);
  h0.redeg((n << 1) - 1);
  ntt.fft(h0.base(), t + 1);
  Poly h0g0 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i) h0g0[i] = h0[i] * (long long)nttg[i] % P;
  ntt.fft(h0g0.base(), t + 1, -1);
  Poly h0eps1 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i) h0eps1[i] = h0[i] * (long long)eps1[i] % P;
  ntt.fft(h0eps1.base(), t + 1, -1);
  for (int i = 0; i < n; ++i) {
    h0eps1[i] = operator[](i + n) - h0eps1[i];
    if (h0eps1[i] < 0) h0eps1[i] += P;
  }
  memset(h0eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(h0eps1.base(), t + 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = h0eps1[i] * (long long)nttg[i] % P;
  ntt.fft(h0eps1.base(), t + 1, -1);
  memcpy(h0eps1.base() + n, h0eps1.base(), sizeof(int) << t);
  memset(h0eps1.base(), 0, sizeof(int) << t);
  return (h0g0 + h0eps1).slice(rhs.deg());
}
Poly Poly::ln() const {
  if (deg() == 0) return 0;
  return der().quo(slice(deg() - 1)).integ();
}
pair<Poly, Poly> Poly::sqrti() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    nttg = g;
    ntt.fft(nttg.base(), t + 1, 1);
    nit.inv(g, nttg, h, t);
  }
  return make_pair(g.slice(deg()), h.slice(deg()));
}
Poly Poly::sqrt() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
      nit.inv(g, nttg, h, t);
    }
  }
  return g.slice(deg());
}
Poly Poly::exp() const {
  Poly g = 1, h = 1, nttg = {1, 1};
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.exp(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      nttg.redeg((4 << t) - 1);
      ntt.fft(nttg.base(), t + 2);
      Poly f2n = zeroes((2 << t) - 1);
      for (int i = 0; i < (2 << t); ++i) f2n[i] = nttg[i << 1];
      nit.inv(g, f2n, h, t);
    } else {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
    }
  }
  return g.slice(deg());
}
Poly Poly::exp(int k) const {
  int lead, lz = 0;
  while (lz < deg() && !a[lz]) ++lz;
  if (lz == deg() && !a[lz]) return *this;
  lead = a[lz];
  if (lz * (long long)k > deg()) return zeroes(deg());
  Poly part =
      Poly(vector<int>(a.begin() + lz, a.begin() + deg() - lz * (k - 1) + 1)) *
      nt.inv(lead);
  part = (part.ln() * k).exp() * mpow(lead, k);
  vector<int> ret(deg() + 1);
  memcpy(ret.begin().base() + lz * k, part.base(),
         sizeof(int) * (deg() - lz * k + 1));
  return ret;
}
Poly Poly::operator/(const Poly& rhs) const {
  int n = deg(), m = rhs.deg();
  if (n < m) return 0;
  Poly ta(vector<int>(a.rbegin(), a.rend())),
      tb(vector<int>(rhs.a.rbegin(), rhs.a.rend()));
  ta.redeg(n - m);
  tb.redeg(n - m);
  Poly q = ta.quo(tb);
  reverse(q.a.begin(), q.a.end());
  return q;
}
pair<Poly, Poly> Poly::div(const Poly& rhs) const {
  if (deg() < rhs.deg()) return make_pair(0, rhs);
  int n = deg(), m = rhs.deg();
  Poly q = operator/(rhs), r;
  int lgn = 0;
  while ((1 << lgn) < rhs.deg()) ++lgn;
  int t = (1 << lgn) - 1;
  r = zeroes(t);
  Poly tmp = zeroes(t);
  for (int i = 0; i <= m; ++i)
    if ((r[i & t] += rhs[i]) >= P) r[i & t] -= P;
  for (int i = 0; i <= n - m; ++i)
    if ((tmp[i & t] += q[i]) >= P) tmp[i & t] -= P;
  ntt.fft(r.base(), lgn, 1);
  ntt.fft(tmp.base(), lgn, 1);
  for (int i = 0; i <= t; ++i) tmp[i] = tmp[i] * (long long)r[i] % P;
  ntt.fft(tmp.base(), lgn, -1);
  memset(r.base(), 0, sizeof(int) << lgn);
  for (int i = 0; i <= n; ++i)
    if ((r[i & t] += a[i]) >= P) r[i & t] -= P;
  for (int i = 0; i < m; ++i)
    if ((r[i] -= tmp[i]) < 0) r[i] += P;
  return make_pair(q, r.slice(m - 1));
}
Poly Poly::operator%(const Poly& rhs) const {
  if (deg() < rhs.deg()) return *this;
  return div(rhs).second;
}
using namespace std;
int F(const vector<int>& B, int K) {
  function<Poly(int, int)> prod = [&](int l, int r) {
    if (l == r) return Poly{1, B[l]};
    int mid = (l + r) >> 1;
    return prod(l, mid) * prod(mid + 1, r);
  };
  Poly ret = prod(0, B.size() - 1);
  return ret[K];
}
int main() {
  int N, K;
  scanf("%d%d", &N, &K);
  vector<int> a(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &a[i]);
    a[i] %= P;
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int opt, q, x, y, d;
    scanf("%d%d%d%d", &opt, &q, &x, &y);
    if (opt == 1) {
      vector<int> tr = a;
      tr[x - 1] = y % P;
      for (int i = 0; i < N; ++i) tr[i] = norm(P + q - tr[i]);
      printf("%d\n", F(tr, K));
    } else {
      scanf("%d", &d);
      vector<int> tr = a;
      d %= P;
      for (int i = x - 1; i < y; ++i) tr[i] = norm(tr[i] + d);
      for (int i = 0; i < N; ++i) tr[i] = norm(P + q - tr[i]);
      printf("%d\n", F(tr, K));
    }
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353, R = 3;
int mpow(int x, int k, int p = P) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = ret * (long long)x % p;
    x = x * (long long)x % p;
    k >>= 1;
  }
  return ret;
}
int norm(int x) { return x >= P ? (x - P) : x; }
struct NumberTheory {
  mt19937 rng;
  NumberTheory()
      : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
  void _exGcd(int a, int b, int& x, int& y) {
    if (!b) {
      x = 1;
      y = 0;
      return;
    }
    _exGcd(b, a % b, y, x);
    y -= a / b * x;
  }
  int inv(int a, int p = P) {
    int x, y;
    _exGcd(a, p, x, y);
    if (x < 0) x += p;
    return x;
  }
  template <class Integer>
  bool quadRes(Integer a, Integer b) {
    if (a <= 1) return true;
    while (a % 4 == 0) a /= 4;
    if (a % 2 == 0) return (b % 8 == 1 || b % 8 == 7) == quadRes(a / 2, b);
    return ((a - 1) % 4 == 0 || (b - 1) % 4 == 0) == quadRes(b % a, a);
  }
  int sqrt(int x, int p = P) {
    if (p == 2 || x <= 1) return x;
    int w, v, k = (p + 1) / 2;
    do {
      w = rng() % p;
    } while (quadRes(v = int((w * (long long)w - x + p) % p), p));
    pair<int, int> res(1, 0), a(w, 1);
    while (k) {
      if (k & 1)
        res = pair<int, int>((res.first * (long long)a.first +
                              res.second * (long long)a.second % p * v) %
                                 p,
                             (res.first * (long long)a.second +
                              res.second * (long long)a.first) %
                                 p);
      if (k >>= 1)
        a = pair<int, int>((a.first * (long long)a.first +
                            a.second * (long long)a.second % p * v) %
                               p,
                           (a.first * (long long)a.second << 1) % p);
    }
    return min(res.first, p - res.first);
  }
} nt;
template <class T, class Comp>
struct AdditionChain {
  int k;
  vector<T> prepare;
  T t, unit;
  Comp comp;
  AdditionChain(const T& t, const Comp& comp, int k, const T& unit = 1)
      : comp(comp), t(t), unit(unit), k(k), prepare(1U << k) {
    prepare[0] = unit;
    for (int i = 1; i < 1 << k; ++i) prepare[i] = comp(prepare[i - 1], t);
  }
  static AdditionChain fourRussians(const T& t, const Comp& comp, int lgn,
                                    const T& unit = 1) {
    lgn = max(lgn, 1);
    int k = 1, lglgn = 1;
    while (2 << lglgn <= lgn) ++lglgn;
    int w = lglgn / lgn;
    while (1 << k < w) ++k;
    return AdditionChain(t, comp, k, unit);
  }
  T pow(int n) const {
    if (n < 1 << k) return prepare[n];
    int r = n & ((1 << k) - 1);
    T step = pow(n >> k);
    for (int rep = 0; rep < k; ++rep) step = comp(step, step);
    return comp(step, prepare[r]);
  }
};
struct Simple {
  int n;
  vector<int> fac, ifac, inv;
  void build(int n) {
    this->n = n;
    fac.resize(n + 1);
    ifac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = 1;
    for (int x = 1; x <= n; ++x) fac[x] = fac[x - 1] * (long long)x % P;
    inv[1] = 1;
    for (int x = 2; x <= n; ++x)
      inv[x] = -(P / x) * (long long)inv[P % x] % P + P;
    ifac[0] = 1;
    for (int x = 1; x <= n; ++x) ifac[x] = ifac[x - 1] * (long long)inv[x] % P;
  }
  Simple() { build(1); }
  void check(int k) {
    int nn = n;
    if (k > nn) {
      while (k > nn) nn <<= 1;
      build(nn);
    }
  }
  int gfac(int k) {
    check(k);
    return fac[k];
  }
  int gifac(int k) {
    check(k);
    return ifac[k];
  }
  int ginv(int k) {
    check(k);
    return inv[k];
  }
  int binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    return gfac(n) * (long long)gifac(m) % P * gifac(n - m) % P;
  }
} simp;
const int L2 = 11;
struct NTT {
  int L;
  int brev[1 << L2];
  vector<int> root;
  NTT() : L(-1) {
    for (int i = 1; i < (1 << L2); ++i)
      brev[i] = brev[i >> 1] >> 1 | ((i & 1) << (L2 - 1));
  }
  void prepRoot(int l) {
    L = l;
    root.resize(1 << L);
    int n = 1 << L;
    int primitive = mpow(R, (P - 1) >> L);
    root[0] = 1;
    for (int i = 1; i < n; ++i)
      root[i] = root[i - 1] * (long long)primitive % P;
  }
  void fft(int* a, int lgn, int d = 1) {
    if (L < lgn) prepRoot(lgn);
    int n = 1 << lgn;
    for (int i = 0; i < n; ++i) {
      int rev = (brev[i >> L2] | (brev[i & ((1 << L2) - 1)] << L2)) >>
                ((L2 << 1) - lgn);
      if (i < rev) swap(a[i], a[rev]);
    }
    int rt = d == 1 ? R : nt.inv(R);
    for (int k = L - 1, t = 1; t < n; t <<= 1, --k) {
      for (int i = 0; i < n; i += t << 1) {
        int *p1 = a + i, *p2 = a + i + t;
        for (int j = 0; j < t; ++j) {
          int x = p2[j] * (long long)root[j << k] % P;
          p2[j] = norm(p1[j] + P - x);
          p1[j] = norm(p1[j] + x);
        }
      }
    }
    if (d == -1) {
      reverse(a + 1, a + n);
      int nv = mpow(n, P - 2);
      for (int i = 0; i < n; ++i) a[i] = a[i] * (long long)nv % P;
    }
  }
} ntt;
struct Poly {
  vector<int> a;
  Poly(int v = 0) : a(1) {
    if ((v %= P) < 0) v += P;
    a[0] = v;
  }
  Poly(const vector<int>& a) : a(a) {}
  Poly(initializer_list<int> init) : a(init) {}
  int operator[](int k) const { return k < a.size() ? a[k] : 0; }
  int& operator[](int k) {
    if (k >= a.size()) a.resize(k + 1);
    return a[k];
  }
  int deg() const { return a.size() - 1; }
  void redeg(int d) { a.resize(d + 1); }
  Poly monic() const;
  Poly sunic() const;
  Poly slice(int d) const {
    if (d < a.size()) return vector<int>(a.begin(), a.begin() + d + 1);
    vector<int> res(a);
    res.resize(d + 1);
    return res;
  }
  int* base() { return a.begin().base(); }
  const int* base() const { return a.begin().base(); }
  Poly println(FILE* fp) const {
    fprintf(fp, "%d", a[0]);
    for (int i = 1; i < a.size(); ++i) fprintf(fp, " %d", a[i]);
    fputc('\n', fp);
    return *this;
  }
  Poly operator+(const Poly& rhs) const {
    vector<int> res(max(a.size(), rhs.a.size()));
    for (int i = 0; i < res.size(); ++i)
      if ((res[i] = operator[](i) + rhs[i]) >= P) res[i] -= P;
    return res;
  }
  Poly operator-() const {
    Poly ret(a);
    for (int i = 0; i < a.size(); ++i)
      if (ret[i]) ret[i] = P - ret[i];
    return ret;
  }
  Poly operator-(const Poly& rhs) const { return operator+(-rhs); }
  Poly operator*(const Poly& rhs) const;
  Poly operator/(const Poly& rhs) const;
  Poly operator%(const Poly& rhs) const;
  Poly der() const;
  Poly integ() const;
  Poly inv() const;
  Poly sqrt() const;
  Poly ln() const;
  Poly exp() const;
  pair<Poly, Poly> sqrti() const;
  Poly quo(const Poly& rhs) const;
  pair<Poly, Poly> iquo(const Poly& rhs) const;
  pair<Poly, Poly> div(const Poly& rhs) const;
  Poly taylor(int k) const;
  Poly pow(int k) const;
  Poly exp(int k) const;
};
Poly zeroes(int deg) { return vector<int>(deg + 1); }
struct Newton {
  void inv(const Poly& f, const Poly& nttf, Poly& g, const Poly& nttg, int t) {
    int n = 1 << t;
    Poly prod = nttf;
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (long long)nttg[i] % P;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i) prod[i] = 0;
    ntt.fft(prod.base(), t + 1, 1);
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (long long)nttg[i] % P;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i) prod[i] = 0;
    g = g - prod;
  }
  void inv(const Poly& f, const Poly& nttf, Poly& g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
  void inv(const Poly& f, Poly& g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly nttf = f;
    nttf.redeg((2 << t) - 1);
    ntt.fft(nttf.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
  void sqrt(const Poly& f, Poly& g, Poly& nttg, Poly& h, int t) {
    for (int i = 0; i < (1 << t); ++i) nttg[i] = mpow(nttg[i], 2);
    ntt.fft(nttg.base(), t, -1);
    nttg = nttg - f;
    for (int i = 0; i < (1 << t); ++i)
      if ((nttg[i + (1 << t)] += nttg[i]) >= P) nttg[i + (1 << t)] -= P;
    memset(nttg.base(), 0, sizeof(int) << t);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly tmp = h;
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) tmp[i] = tmp[i] * (long long)nttg[i] % P;
    ntt.fft(tmp.base(), t + 1, -1);
    memset(tmp.base(), 0, sizeof(int) << t);
    g = g - tmp * nt.inv(2);
  }
  void exp(const Poly& f, Poly& g, Poly& nttg, Poly& h, int t) {
    Poly ntth(h);
    ntt.fft(ntth.base(), t, 1);
    Poly dg = g.der().slice((1 << t) - 1);
    ntt.fft(dg.base(), t, 1);
    Poly tmp = zeroes((1 << t) - 1);
    for (int i = 0; i < (1 << t); ++i) {
      tmp[i] = nttg[i << 1] * (long long)ntth[i] % P;
      dg[i] = dg[i] * (long long)ntth[i] % P;
    }
    ntt.fft(tmp.base(), t, -1);
    ntt.fft(dg.base(), t, -1);
    if (--tmp[0] < 0) tmp[0] = P - 1;
    dg.redeg((2 << t) - 1);
    Poly df0 = f.der().slice((1 << t) - 1);
    df0[(1 << t) - 1] = 0;
    for (int i = 0; i < (1 << t); ++i) {
      if ((dg[i | 1 << t] = dg[i] - df0[i]) < 0) dg[i | 1 << t] += P;
    }
    memcpy(dg.base(), df0.base(), sizeof(int) * ((1 << t) - 1));
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    df0.redeg((2 << t) - 1);
    ntt.fft(df0.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) df0[i] = df0[i] * (long long)tmp[i] % P;
    ntt.fft(df0.base(), t + 1, -1);
    memcpy(df0.base() + (1 << t), df0.base(), sizeof(int) << t);
    memset(df0.base(), 0, sizeof(int) << t);
    dg = (dg - df0).integ().slice((2 << t) - 1) - f;
    ntt.fft(dg.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i) tmp[i] = dg[i] * (long long)nttg[i] % P;
    ntt.fft(tmp.base(), t + 1, -1);
    g.redeg((2 << t) - 1);
    for (int i = 1 << t; i < (2 << t); ++i)
      if (tmp[i]) g[i] = P - tmp[i];
  }
} nit;
struct EvaluationHelper {
  int _t, _lim;
  vector<int> _tmp, _res, _tmpy;
  vector<Poly> _h, _r;
  EvaluationHelper() {}
  void _solve(int l, int r) {
    if (l == r) {
      _h[_t] = Poly{(P - _tmp[l]) % P, 1};
      ++_t;
      return;
    }
    int p = _t++;
    int ls = _t, mid = (l + r) >> 1;
    _solve(l, mid);
    int rs = _t;
    _solve(mid + 1, r);
    if ((r - l + 1) <= _lim) _h[p] = _h[ls] * _h[rs];
  }
  void _solve2(int l, int r) {
    if ((r - l + 1) <= _lim) _r[_t] = _r[_t] % _h[_t];
    if (l == r) {
      _res[l] = _r[_t][0];
      ++_t;
      return;
    }
    int p = _t++, mid = (l + r) >> 1;
    _r[_t] = _r[p] % _h[_t];
    _solve2(l, mid);
    _r[_t] = _r[p] % _h[_t];
    _solve2(mid + 1, r);
  }
  void _divideConquer(int l, int r) {
    if (l == r) {
      _r[_t] = nt.inv(_res[l]) * (long long)_tmpy[l] % P;
      ++_t;
      return;
    }
    int p = _t++, mid = (l + r) >> 1;
    int ls = _t;
    _divideConquer(l, mid);
    int rs = _t;
    _divideConquer(mid + 1, r);
    _r[p] = _r[ls] * _h[rs] + _r[rs] * _h[ls];
  }
  vector<int> evaluate(const Poly& p, const vector<int>& x) {
    if (x.empty()) return vector<int>();
    int n = x.size();
    _lim = n;
    _tmp = x;
    _h.resize(n * 2 - 1);
    _r.resize(n * 2 - 1);
    _t = 0;
    _solve(0, n - 1);
    _res.resize(n);
    _t = 0;
    _r[0] = p;
    _solve2(0, n - 1);
    _tmp.clear();
    _h.clear();
    _r.clear();
    return _res;
  }
  Poly interpolate(const vector<pair<int, int> >& points) {
    int n = points.size();
    _tmp.resize(n);
    for (int i = 0; i < n; ++i) _tmp[i] = points[i].first;
    _lim = n;
    _h.resize(n * 2 - 1);
    _r.resize(n * 2 - 1);
    _t = 0;
    _solve(0, n - 1);
    _res.resize(n);
    _t = 0;
    _r[0] = _h[0].der();
    _solve2(0, n - 1);
    _tmp.clear();
    _tmpy.resize(n);
    for (int i = 0; i < n; ++i) _tmpy[i] = points[i].second;
    _t = 0;
    _divideConquer(0, n - 1);
    return _r[0];
  }
} eh;
Poly operator"" _z(unsigned long long a) { return {0, (int)a}; }
Poly operator+(int v, const Poly& rhs) { return Poly(v) + rhs; }
Poly Poly::operator*(const Poly& rhs) const {
  int n = deg(), m = rhs.deg();
  if (n <= 10 || m <= 10) {
    Poly ret = zeroes(n + m);
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
        ret[i + j] = (ret[i + j] + a[i] * (long long)rhs[j]) % P;
    return ret;
  }
  n += m;
  int l = 0;
  while ((1 << l) <= n) ++l;
  vector<int> res(1 << l), tmp(1 << l);
  memcpy(res.begin().base(), base(), a.size() * sizeof(int));
  ntt.fft(res.begin().base(), l, 1);
  memcpy(tmp.begin().base(), rhs.base(), rhs.a.size() * sizeof(int));
  ntt.fft(tmp.begin().base(), l, 1);
  for (int i = 0; i < (1 << l); ++i) res[i] = res[i] * (long long)tmp[i] % P;
  ntt.fft(res.begin().base(), l, -1);
  res.resize(n + 1);
  return res;
}
Poly Poly::inv() const {
  Poly g = nt.inv(a[0]);
  for (int t = 0; (1 << t) <= deg(); ++t) nit.inv(slice((2 << t) - 1), g, t);
  g.redeg(deg());
  return g;
}
Poly Poly::taylor(int k) const {
  int n = deg();
  Poly t = zeroes(n);
  simp.check(n);
  for (int i = 0; i <= n; ++i) t[n - i] = a[i] * (long long)simp.fac[i] % P;
  int pw = 1;
  Poly help = vector<int>(simp.ifac.begin(), simp.ifac.begin() + n + 1);
  for (int i = 0; i <= n; ++i) {
    help[i] = help[i] * (long long)pw % P;
    pw = pw * (long long)k % P;
  }
  t = t * help;
  for (int i = 0; i <= n; ++i) help[i] = t[n - i] * (long long)simp.ifac[i] % P;
  return help;
}
Poly Poly::pow(int k) const {
  if (k == 0) return 1;
  if (k == 1) return *this;
  int n = deg() * k;
  int lgn = 0;
  while ((1 << lgn) <= n) ++lgn;
  vector<int> val = a;
  val.resize(1 << lgn);
  ntt.fft(val.begin().base(), lgn, 1);
  for (int i = 0; i < (1 << lgn); ++i) val[i] = mpow(val[i], k);
  ntt.fft(val.begin().base(), lgn, -1);
  return val;
}
Poly Poly::der() const {
  if (deg() == 0) return 0;
  vector<int> res(deg());
  for (int i = 0; i < deg(); ++i) res[i] = a[i + 1] * (long long)(i + 1) % P;
  return res;
}
Poly Poly::integ() const {
  vector<int> res(deg() + 2);
  simp.check(deg() + 1);
  for (int i = 0; i <= deg(); ++i)
    res[i + 1] = a[i] * (long long)simp.inv[i + 1] % P;
  return res;
}
Poly Poly::quo(const Poly& rhs) const {
  if (rhs.deg() == 0) return a[0] * (long long)nt.inv(rhs[0]) % P;
  Poly g = nt.inv(rhs[0]);
  int t = 0, n;
  for (n = 1; (n << 1) <= rhs.deg(); ++t, n <<= 1)
    nit.inv(rhs.slice((n << 1) - 1), g, t);
  Poly nttg = g;
  nttg.redeg((n << 1) - 1);
  ntt.fft(nttg.base(), t + 1, 1);
  Poly eps1 = rhs.slice((n << 1) - 1);
  ntt.fft(eps1.base(), t + 1, 1);
  for (int i = 0; i < (n << 1); ++i) eps1[i] = eps1[i] * (long long)nttg[i] % P;
  ntt.fft(eps1.base(), t + 1, -1);
  memcpy(eps1.base(), eps1.base() + n, sizeof(int) << t);
  memset(eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(eps1.base(), t + 1, 1);
  Poly h0 = slice(n - 1);
  h0.redeg((n << 1) - 1);
  ntt.fft(h0.base(), t + 1);
  Poly h0g0 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i) h0g0[i] = h0[i] * (long long)nttg[i] % P;
  ntt.fft(h0g0.base(), t + 1, -1);
  Poly h0eps1 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i) h0eps1[i] = h0[i] * (long long)eps1[i] % P;
  ntt.fft(h0eps1.base(), t + 1, -1);
  for (int i = 0; i < n; ++i) {
    h0eps1[i] = operator[](i + n) - h0eps1[i];
    if (h0eps1[i] < 0) h0eps1[i] += P;
  }
  memset(h0eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(h0eps1.base(), t + 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = h0eps1[i] * (long long)nttg[i] % P;
  ntt.fft(h0eps1.base(), t + 1, -1);
  memcpy(h0eps1.base() + n, h0eps1.base(), sizeof(int) << t);
  memset(h0eps1.base(), 0, sizeof(int) << t);
  return (h0g0 + h0eps1).slice(rhs.deg());
}
Poly Poly::ln() const {
  if (deg() == 0) return 0;
  return der().quo(slice(deg() - 1)).integ();
}
pair<Poly, Poly> Poly::sqrti() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    nttg = g;
    ntt.fft(nttg.base(), t + 1, 1);
    nit.inv(g, nttg, h, t);
  }
  return make_pair(g.slice(deg()), h.slice(deg()));
}
Poly Poly::sqrt() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
      nit.inv(g, nttg, h, t);
    }
  }
  return g.slice(deg());
}
Poly Poly::exp() const {
  Poly g = 1, h = 1, nttg = {1, 1};
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.exp(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      nttg.redeg((4 << t) - 1);
      ntt.fft(nttg.base(), t + 2);
      Poly f2n = zeroes((2 << t) - 1);
      for (int i = 0; i < (2 << t); ++i) f2n[i] = nttg[i << 1];
      nit.inv(g, f2n, h, t);
    } else {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
    }
  }
  return g.slice(deg());
}
Poly Poly::exp(int k) const {
  int lead, lz = 0;
  while (lz < deg() && !a[lz]) ++lz;
  if (lz == deg() && !a[lz]) return *this;
  lead = a[lz];
  if (lz * (long long)k > deg()) return zeroes(deg());
  Poly part =
      Poly(vector<int>(a.begin() + lz, a.begin() + deg() - lz * (k - 1) + 1)) *
      nt.inv(lead);
  part = (part.ln() * k).exp() * mpow(lead, k);
  vector<int> ret(deg() + 1);
  memcpy(ret.begin().base() + lz * k, part.base(),
         sizeof(int) * (deg() - lz * k + 1));
  return ret;
}
Poly Poly::operator/(const Poly& rhs) const {
  int n = deg(), m = rhs.deg();
  if (n < m) return 0;
  Poly ta(vector<int>(a.rbegin(), a.rend())),
      tb(vector<int>(rhs.a.rbegin(), rhs.a.rend()));
  ta.redeg(n - m);
  tb.redeg(n - m);
  Poly q = ta.quo(tb);
  reverse(q.a.begin(), q.a.end());
  return q;
}
pair<Poly, Poly> Poly::div(const Poly& rhs) const {
  if (deg() < rhs.deg()) return make_pair(0, rhs);
  int n = deg(), m = rhs.deg();
  Poly q = operator/(rhs), r;
  int lgn = 0;
  while ((1 << lgn) < rhs.deg()) ++lgn;
  int t = (1 << lgn) - 1;
  r = zeroes(t);
  Poly tmp = zeroes(t);
  for (int i = 0; i <= m; ++i)
    if ((r[i & t] += rhs[i]) >= P) r[i & t] -= P;
  for (int i = 0; i <= n - m; ++i)
    if ((tmp[i & t] += q[i]) >= P) tmp[i & t] -= P;
  ntt.fft(r.base(), lgn, 1);
  ntt.fft(tmp.base(), lgn, 1);
  for (int i = 0; i <= t; ++i) tmp[i] = tmp[i] * (long long)r[i] % P;
  ntt.fft(tmp.base(), lgn, -1);
  memset(r.base(), 0, sizeof(int) << lgn);
  for (int i = 0; i <= n; ++i)
    if ((r[i & t] += a[i]) >= P) r[i & t] -= P;
  for (int i = 0; i < m; ++i)
    if ((r[i] -= tmp[i]) < 0) r[i] += P;
  return make_pair(q, r.slice(m - 1));
}
Poly Poly::operator%(const Poly& rhs) const {
  if (deg() < rhs.deg()) return *this;
  return div(rhs).second;
}
using namespace std;
int F(const vector<int>& B, int K) {
  function<Poly(int, int)> prod = [&](int l, int r) {
    if (l == r) return Poly{1, B[l]};
    int mid = (l + r) >> 1;
    return prod(l, mid) * prod(mid + 1, r);
  };
  Poly ret = prod(0, B.size() - 1);
  return ret[K];
}
int main() {
  int N, K;
  scanf("%d%d", &N, &K);
  vector<int> a(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &a[i]);
    a[i] %= P;
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int opt, q, x, y, d;
    scanf("%d%d%d%d", &opt, &q, &x, &y);
    if (opt == 1) {
      vector<int> tr = a;
      tr[x - 1] = y % P;
      for (int i = 0; i < N; ++i) tr[i] = norm(P + q - tr[i]);
      printf("%d\n", F(tr, K));
    } else {
      scanf("%d", &d);
      vector<int> tr = a;
      d %= P;
      for (int i = x - 1; i < y; ++i) tr[i] = norm(tr[i] + d);
      for (int i = 0; i < N; ++i) tr[i] = norm(P + q - tr[i]);
      printf("%d\n", F(tr, K));
    }
  }
  return 0;
}

```