#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); const vi DX = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) const vi DY = { 0, 1, 0, -1 }; int INF = 1001001001; ll INFL = 4004004003104004004LL; // (int)INFL = 1010931620; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順) #define repis(i, set) for(int i = lsb(set), bset##i = set; i >= 0; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 // 汎用関数の定義 template inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T get(T set, int i) { return (set >> i) & T(1); } // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } using vm = vector; using vvm = vector; using vvvm = vector; using vvvvm = vector; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define dump(...) #define dumpel(v) #define dump_list(v) #define dump_mat(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) while (1) cout << "OLE"; } #endif //【階乗など(法が大きな素数)】 /* * Factorial_mint(int N) : O(n) * N まで計算可能として初期化する. * * mint fact(int n) : O(1) * n! を返す. * * mint fact_inv(int n) : O(1) * 1/n! を返す(n が負なら 0 を返す) * * mint inv(int n) : O(1) * 1/n を返す. * * mint perm(int n, int r) : O(1) * 順列の数 nPr を返す. * * mint bin(int n, int r) : O(1) * 二項係数 nCr を返す. * * mint mul(vi rs) : O(|rs|) * 多項係数 nC[rs] を返す.(n = Σrs) * * mint hom(int n, int r) : O(1) * 重複組合せの数 nHr = n+r-1Cr を返す(0H0 = 1 とする) */ class Factorial_mint { int n_max; // 階乗と階乗の逆数の値を保持するテーブル vm fac, fac_inv; public: // n! までの階乗とその逆数を前計算しておく.O(n) Factorial_mint(int n) : n_max(n), fac(n + 1), fac_inv(n + 1) { // verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b fac[0] = 1; repi(i, 1, n) fac[i] = fac[i - 1] * i; fac_inv[n] = fac[n].inv(); repir(i, n - 1, 0) fac_inv[i] = fac_inv[i + 1] * (i + 1); } Factorial_mint() : n_max(0) {} // ダミー // n! を返す. mint fact(int n) const { // verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b Assert(0 <= n && n <= n_max); return fac[n]; } // 1/n! を返す(n が負なら 0 を返す) mint fact_inv(int n) const { // verify : https://atcoder.jp/contests/abc289/tasks/abc289_h Assert(n <= n_max); if (n < 0) return 0; return fac_inv[n]; } // 1/n を返す. mint inv(int n) const { // verify : https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d Assert(0 < n && n <= n_max); return fac[n - 1] * fac_inv[n]; } // 順列の数 nPr を返す. mint perm(int n, int r) const { // verify : https://atcoder.jp/contests/abc172/tasks/abc172_e Assert(n <= n_max); if (r < 0 || n - r < 0) return 0; return fac[n] * fac_inv[n - r]; } // 二項係数 nCr を返す. mint bin(int n, int r) const { // verify : https://atcoder.jp/contests/abc034/tasks/abc034_c Assert(n <= n_max); if (r < 0 || n - r < 0) return 0; return fac[n] * fac_inv[r] * fac_inv[n - r]; } // 多項係数 nC[rs] を返す. mint mul(const vi& rs) const { // verify : https://yukicoder.me/problems/no/2141 if (*min_element(all(rs)) < 0) return 0; int n = accumulate(all(rs), 0); Assert(n <= n_max); mint res = fac[n]; repe(r, rs) res *= fac_inv[r]; return res; } // 重複組合せの数 nHr = n+r-1Cr を返す(0H0 = 1 とする) mint hom(int n, int r) { // verify : https://mojacoder.app/users/riantkb/problems/toj_ex_2 if (n == 0) return (int)(r == 0); Assert(n + r - 1 <= n_max); if (r < 0 || n - 1 < 0) return 0; return fac[n + r - 1] * fac_inv[r] * fac_inv[n - 1]; } }; //【幅優先探索(動的)】O(n + m)(遅い) /* * st から到達可能な頂点 t のリストを返す.nxt(s) は s の次に訪れることのできる頂点のリストを返す. * 探索は lim ms だけ続ける. */ template set get_reachable_set(T st, const function(T)>& nxt, int lim = (int)1e9) { // verify : https://atcoder.jp/contests/agc045/tasks/agc045_c auto start = chrono::system_clock::now(); set vs; // st から到達可能な頂点のリスト vs.insert(st); queue que; // 次に探索する頂点を入れておくキュー que.push(st); while (!que.empty()) { // 未探索の頂点 s を得る. auto s = que.front(); que.pop(); repe(t, nxt(s)) { // t が発見済みの頂点なら何もしない. if (vs.count(t)) continue; // t に到達したことを記録する. vs.insert(t); // 未探索の頂点として t を追加する. que.push(t); } auto now = chrono::system_clock::now(); auto msec = chrono::duration_cast(now - start).count(); if (msec >= lim) break; } return vs; /* nxt の定義の雛形 using T = ll; function(T)> nxt = [&](T s) { vector res; return res; }; */ } // 入力が N, K, M のみと少ないので,まずは愚直を書いてみる. void zikken() { using T = vector; function(T)> nxt = [&](T s) { vector res; int n = sz(s); rep(i, n - 2) { { vector t; rep(j, i) t.push_back(s[j]); t.push_back(s[i] + s[i + 1] + s[i + 2]); repi(j, i + 3, n - 1) t.push_back(s[j]); res.push_back(t); } { vector t; rep(j, i) t.push_back(s[j]); t.push_back(s[i + 2] + s[i + 1] + s[i]); repi(j, i + 3, n - 1) t.push_back(s[j]); res.push_back(t); } } return res; }; repi(n, 1, 20) { vector ini(n); rep(i, n) ini[i] += 'a' + i; auto res = get_reachable_set(ini, nxt); vi cnt(n + 1); repe(s, res) cnt[sz(s)]++; dump_list(cnt); } exit(0); } /* K = 3: {0, 1} {0, 0, 1} {0, 2, 0, 1} {0, 0, 4, 0, 1} {0, 8, 0, 6, 0, 1} {0, 0, 20, 0, 8, 0, 1} {0, 42, 0, 36, 0, 10, 0, 1} {0, 0, 116, 0, 56, 0, 12, 0, 1} {0, 252, 0, 230, 0, 80, 0, 14, 0, 1} {0, 0, 736, 0, 392, 0, 108, 0, 16, 0, 1} {0, 1636, 0, 1548, 0, 610, 0, 140, 0, 18, 0, 1} {0, 0, 4952, 0, 2800, 0, 892, 0, 176, 0, 20, 0, 1} {0, 11188, 0, 10836, 0, 4620, 0, 1246, 0, 216, 0, 22, 0, 1} {0, 0, 34716, 0, 20432, 0, 7152, 0, 1680, 0, 260, 0, 24, 0, 1} {0, 79386, 0, 78152, 0, 35172, 0, 10556, 0, 2202, 0, 308, 0, 26, 0, 1} {0, 0, 250868, 0, 151944, 0, 56808, 0, 15008, 0, 2820, 0, 360, 0, 28, 0, 1} {0, 579020, 0, 576918, 0, 270060, 0, 87444, 0, 20700, 0, 3542, 0, 416, 0, 30, 0, 1} {0, 0, 1855520, 0, 1148296, 0, 450692, 0, 129568, 0, 27840, 0, 4376, 0, 476, 0, 32, 0, 1} {0, 4314300, 0, 4338540, 0, 2092530, 0, 717024, 0, 186084, 0, 36652, 0, 5330, 0, 540, 0, 34, 0, 1} OEIS で検索しても見つからない. しょうがないのでまずは F 問題を真面目に考えよう. */ /* * F 問題を真面目に考えた後 * * 1 つの連結成分で,最後に右向きに重ねた場合の母関数を g(z) とすると, * z + (2 g - z) g(z)^(m-1) = g(z) * なる関数方程式が得られる.これを z について解くと * z = (g(z) - 2 g(z)^m) / (1 - g(z)^(m-1)) * となるので,g(z) の逆関数は * h(z) = (z - 2 z^m) / (1 - z^(m-1)) * である.求めたいものは * [z^n] (2 g(z) - z)^k * = Σj∈[0..k] bin(k, j) 2^j (-1)^(k-j) [z^n] g(z)^j z^(k-j) * = Σj∈[0..k] bin(k, j) 2^j (-1)^(k-j) [z^(n-k+j)] g(z)^j * である.ラグランジュの反転公式より * [z^n] g(z)^k * = k/n [z^(n-k)](z / h(z))^n * = k/n [z^(n-k)](z (1 - z^(m-1)) / (z - 2 z^m))^n * = k/n [z^(n-k)]((1 - z^(m-1)) / (1 - 2 z^(m-1)))^n * = k/n [z^(n-k)]((1 - z^(m-1))^n (1 - 2 z^(m-1)))^(-n) * = k/n [z^((n-k)/(m-1))]((1 - z)^n (1 - 2 z))^(-n) * となる. * L = (n-k)/(m-1) * とおくと,二項定理および負の二項定理より * [z^n] g(z)^k * = k/n Σi∈[0..L] (-1)^(L-i) bin(n, L-i) 2^i bin(i+n-1, n-1) * を得る.ひとまずここまで合ってるかチェックしておく. */ vm TLE(int n, int m, const vi& ks) { Factorial_mint fm(2 * n + 10); vm pow2(2 * n + 11); pow2[0] = 1; rep(i, 2 * n + 10) pow2[i + 1] = pow2[i] * 2; vm res; repe(k, ks) { // O(q) if (k == n) { res.push_back(1); continue; } if ((n - k) % (m - 1) != 0) { res.push_back(0); continue; } int L = (n - k) / (m - 1); mint val = 0; repi(j, 0, k) { // O(k) mint val2 = 0; repi(i, 0, L) { // O(n / m) val2 += ((L - i) & 1 ? -1 : 1) * fm.bin(n - k + j, L - i) * pow2[i] * fm.bin(n - k + j + i - 1, i); } val += fm.bin(k, j) * pow2[j] * ((k - j) & 1 ? -1 : 1) * j * fm.inv(n - k + j) * val2; } res.push_back(val); } return res; } //【行列】 /* * Matrix(int n, int m) : O(n m) * n×m 零行列で初期化する. * * Matrix(int n) : O(n^2) * n×n 単位行列で初期化する. * * Matrix(vvT a) : O(n m) * 二次元配列 a[0..n)[0..m) の要素で初期化する. * * bool empty() : O(1) * 行列が空かを返す. * * A + B : O(n m) * n×m 行列 A, B の和を返す.+= も使用可. * * A - B : O(n m) * n×m 行列 A, B の差を返す.-= も使用可. * * c * A / A * c : O(n m) * n×m 行列 A とスカラー c のスカラー積を返す.*= も使用可. * * A * x : O(n m) * n×m 行列 A と n 次元列ベクトル x の積を返す. * * x * A : O(n m) * m 次元行ベクトル x と n×m 行列 A の積を返す. * * A * B : O(n m l) * n×m 行列 A と m×l 行列 B の積を返す. * * Mat pow(ll d) : O(n^3 log d) * 自身を d 乗した行列を返す. */ template struct Matrix { int n, m; // 行列のサイズ(n 行 m 列) vector> v; // 行列の成分 // n×m 零行列で初期化する. Matrix(int n, int m) : n(n), m(m), v(n, vector(m)) {} // n×n 単位行列で初期化する. Matrix(int n) : n(n), m(n), v(n, vector(n)) { rep(i, n) v[i][i] = T(1); } // 二次元配列 a[0..n)[0..m) の要素で初期化する. Matrix(const vector>& a) : n(sz(a)), m(sz(a[0])), v(a) {} Matrix() : n(0), m(0) {} // 代入 Matrix(const Matrix&) = default; Matrix& operator=(const Matrix&) = default; // アクセス inline vector const& operator[](int i) const { return v[i]; } inline vector& operator[](int i) { // verify : https://judge.yosupo.jp/problem/matrix_product // inline を付けて [] でアクセスするとなぜか v[] への直接アクセスより速くなった. return v[i]; } // 入力 friend istream& operator>>(istream& is, Matrix& a) { rep(i, a.n) rep(j, a.m) is >> a.v[i][j]; return is; } // 行の追加 void push_back(const vector& a) { Assert(sz(a) == m); v.push_back(a); n++; } // 行の削除 void pop_back() { Assert(n > 0); v.pop_back(); n--; } void resize(int n_) { v.resize(n_); n = n_; } // 空か bool empty() const { return min(n, m) == 0; } // 比較 bool operator==(const Matrix& b) const { return n == b.n && m == b.m && v == b.v; } bool operator!=(const Matrix& b) const { return !(*this == b); } // 加算,減算,スカラー倍 Matrix& operator+=(const Matrix& b) { rep(i, n) rep(j, m) v[i][j] += b[i][j]; return *this; } Matrix& operator-=(const Matrix& b) { rep(i, n) rep(j, m) v[i][j] -= b[i][j]; return *this; } Matrix& operator*=(const T& c) { rep(i, n) rep(j, m) v[i][j] *= c; return *this; } Matrix operator+(const Matrix& b) const { return Matrix(*this) += b; } Matrix operator-(const Matrix& b) const { return Matrix(*this) -= b; } Matrix operator*(const T& c) const { return Matrix(*this) *= c; } friend Matrix operator*(const T& c, const Matrix& a) { return a * c; } Matrix operator-() const { return Matrix(*this) *= T(-1); } // 行列ベクトル積 : O(m n) vector operator*(const vector& x) const { vector y(n); rep(i, n) rep(j, m) y[i] += v[i][j] * x[j]; return y; } // ベクトル行列積 : O(m n) friend vector operator*(const vector& x, const Matrix& a) { vector y(a.m); rep(i, a.n) rep(j, a.m) y[j] += x[i] * a[i][j]; return y; } // 積:O(n^3) Matrix operator*(const Matrix& b) const { // verify : https://judge.yosupo.jp/problem/matrix_product Matrix res(n, b.m); rep(i, res.n) rep(j, res.m) rep(k, m) res[i][j] += v[i][k] * b[k][j]; return res; } Matrix& operator*=(const Matrix& b) { *this = *this * b; return *this; } // 累乗:O(n^3 log d) Matrix pow(ll d) const { // verify : https://judge.yosupo.jp/problem/pow_of_matrix Matrix res(n), pow2 = *this; while (d > 0) { if (d & 1) res *= pow2; pow2 *= pow2; d /= 2; } return res; } #ifdef _MSC_VER friend ostream& operator<<(ostream& os, const Matrix& a) { rep(i, a.n) { os << "["; rep(j, a.m) os << a[i][j] << " ]"[j == a.m - 1]; if (i < a.n - 1) os << "\n"; } return os; } #endif }; //【線形方程式】O(n m min(n, m)) /* * 与えられた n×m 行列 A と n 次元ベクトル b に対し, * 線形方程式 A x = b の特殊解 x0(m 次元ベクトル)を返す(なければ空リスト) * また同次形 A x = 0 の解空間の基底(m 次元ベクトル)のリストを xs に格納する. */ template vector gauss_jordan_elimination(const Matrix& A, const vector& b, vector>* xs = nullptr) { // verify : https://judge.yosupo.jp/problem/system_of_linear_equations int n = A.n, m = A.m; // v : 拡大係数行列 (A | b) vector> v(n, vector(m + 1)); rep(i, n) rep(j, m) v[i][j] = A[i][j]; rep(i, n) v[i][m] = b[i]; // pivots[i] : 第 i 行のピボットが第何列にあるか vi pivots; // 注目位置を v[i][j] とする. int i = 0, j = 0; while (i < n && j <= m) { // 注目列の下方の行から非 0 成分を見つける. int i2 = i; while (i2 < n && v[i2][j] == 0) i2++; // 見つからなかったら注目位置を右に移す. if (i2 == n) { j++; continue; } // 見つかったら第 i 行とその行を入れ替える. if (i != i2) swap(v[i], v[i2]); // v[i][j] をピボットに選択する. pivots.push_back(j); // v[i][j] が 1 になるよう第 i 行全体を v[i][j] で割る. T vij_inv = T(1) / v[i][j]; repi(j2, j, m) v[i][j2] *= vij_inv; // 第 i 行以外の第 j 列の成分が全て 0 になるよう第 i 行を定数倍して減じる. rep(i2, n) { if (v[i2][j] == T(0) || i2 == i) continue; T mul = v[i2][j]; repi(j2, j, m) v[i2][j2] -= v[i][j2] * mul; } // 注目位置を右下に移す. i++; j++; } // 最後に見つかったピボットの位置が第 m 列ならば解なし. if (!pivots.empty() && pivots.back() == m) return vector(); // A x = b の特殊解 x0 の構成(任意定数は全て 0 にする) vector x0(m); int rnk = sz(pivots); rep(i, rnk) x0[pivots[i]] = v[i][m]; // 同次形 A x = 0 の一般解 {x} の基底の構成(任意定数を 1-hot にする) if (xs != nullptr) { xs->clear(); int i = 0; rep(j, m) { if (i < rnk && j == pivots[i]) { i++; continue; } vector x(m, T(0)); x[j] = 1; rep(i2, i) x[pivots[i2]] = -v[i2][j]; xs->emplace_back(move(x)); } } return x0; } //【変数係数線形漸化式の発見】O(n L^2 D^2 + N (L D + log(mod))) /* * 係数多項式の次数が D 次未満の L 項間漸化式 * Σi∈[0..L) Σj∈[0..D) c(i,j) (n+i)^j a[n+i] = 0 * の存在を仮定して a[0..n) を延長し a[0..N] にする(失敗したら false を返す) */ bool p_recursive(int N, vm& a, int L, int D, vm* coef = nullptr) { // verify : https://atcoder.jp/contests/abc222/tasks/abc222_h int n = sz(a); if (N <= n - 1) { a.resize(N + 1); return true; } if (n - L < 0) return false; Matrix mat(n - L + 2, L * D); repi(n0, 0, n - L) { rep(i, L) rep(j, D) { mat[n0][i * D + j] = mint(n0 + i).pow(j) * a[n0 + i]; } } mat[n - L + 1][(L - 1) * D + (D - 1)] = 1; vm vec(n - L + 2); vec.back() = 1; vm c = gauss_jordan_elimination(mat, vec); if (c.empty()) return false; dump(c); a.resize(N + 1); repi(n0, n - L + 1, N - L + 1) { mint num = 0; rep(i, L - 1) { mint pow_n0i = 1; rep(j, D) { num += c[i * D + j] * pow_n0i * a[n0 + i]; pow_n0i *= n0 + i; } } mint dnm = 0; mint pow_n0L = 1; rep(j, D) { dnm += c[(L - 1) * D + j] * pow_n0L; pow_n0L *= n0 + L - 1; } // num + dnm * a[n0 + L - 1] = 0 a[n0 + L - 1] = -num / dnm; } if (coef) *coef = move(c); return true; } // たぶん m=2 のときと同じく P-recursive なので,それで数列を延長する. vm TLE2(int n, int m, const vi& ks) { Factorial_mint fm(2 * n + 10); vm pow2(2 * n + 11); pow2[0] = 1; rep(i, 2 * n + 10) pow2[i + 1] = pow2[i] * 2; vm seq{ 1 }; int L = m + 3, D = m; dump("L, D", L, D); for(int k = n - (m - 1); k > 0; k -= m - 1) { int K = (n - k) / (m - 1); mint val = 0; repi(j, 0, k) { // O(k) mint val2 = 0; repi(i, 0, K) { // O(n / m) val2 += ((K - i) & 1 ? -1 : 1) * fm.bin(n - k + j, K - i) * pow2[i] * fm.bin(n - k + j + i - 1, i); } val += fm.bin(k, j) * pow2[j] * ((k - j) & 1 ? -1 : 1) * j * fm.inv(n - k + j) * val2; } seq.push_back(val); if (sz(seq) - L + 2 >= L * D) break; } dump(seq); p_recursive(n / (m - 1), seq, L, D); vm res; repe(k, ks) { if (k == n) { res.push_back(1); continue; } if ((n - k) % (m - 1) != 0) { res.push_back(0); continue; } int K = (n - k) / (m - 1); res.push_back(seq[K]); } return res; } int main() { // input_from_file("input.txt"); // output_to_file("output.txt"); // zikken(); int n, m, q; cin >> n >> m >> q; vi ks(q); cin >> ks; vm res; if (m <= 10) { res = TLE2(n, m, ks); } else { res = TLE(n, m, ks); } rep(j, q) cout << res[j] << endl; }