#pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; using ld = long double; using i128 = __int128_t; using P = pair; using LP = pair; using LT = tuple; using LT4 = tuple; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector v3l; typedef vector v4l; typedef vector v5l; typedef vector vlp; typedef vector vvlp; typedef vector vlt; typedef vector vvlt; typedef vector vlt4; typedef vector vs; typedef vector vvs; typedef vector vd; typedef vector vvd; typedef vector vb; typedef vector vvb; template using pq = priority_queue; template using mpq = priority_queue, greater>; template class infinity{ public: static constexpr T MAX=numeric_limits::max(); static constexpr T MIN=numeric_limits::min(); static constexpr T val=numeric_limits::max()/2-1e6; static constexpr T mval=numeric_limits::min()/2+1e6; }; const int INF = infinity::val; const ll LINF = infinity::val; const ld DINF = infinity::val; #define _overload5(a, b, c, d, e, name, ...) name #define _overload4(a, b, c, d, name, ...) name #define _overload3(a, b, c, name, ...) name #define _rep0(n) for(ll i = 0; i < (ll)(n); ++i) #define _rep1(i, n) for(ll i = 0; i < (ll)(n); ++i) #define _rep2(i, a, b) for(ll i = (ll)(a); i < (ll)(b); ++i) #define _rep3(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c)) #define rep(...) _overload4(__VA_ARGS__, _rep3, _rep2, _rep1, _rep0)(__VA_ARGS__) #define _per0(n) for(ll i = 0; i < (ll)(n); ++i) #define _per1(i, n) for(ll i = (ll)(n)-1; i >= 0; --i) #define _per2(i, a, b) for(ll i = (ll)(b)-1; i >= (ll)(a); --i) #define _per3(i, a, b, c) for(ll i = (ll)(b)-1; i >= (ll)(a); i -= (ll)(c)) #define rep_r(...) _overload4(__VA_ARGS__, _per3, _per2, _per1, _per0)(__VA_ARGS__) #define _fore0(a) rep(a.size()) #define _fore1(i, a) for(auto &&i : a) #define _fore2(a, b, v) for(auto &&[a, b] : v) #define _fore3(a, b, c, v) for(auto &&[a, b, c] : v) #define _fore4(a, b, c, d, v) for(auto &&[a, b, c, d] : v) #define fore(...) _overload5(__VA_ARGS__, _fore4, _fore3, _fore2, _fore1, _fore0)(__VA_ARGS__) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define rng_of(v, l, r) (v).begin() + l, (v).begin() + r #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define vv(type, name, h, ...) vector> name(h, vector(__VA_ARGS__)) #define v3(type, name, h, w, ...) vector>> name(h, vector>(w, vector(__VA_ARGS__))) #define v4(type, name, a, b, c, ...) vector>>> name(a, vector>>(b, vector>(c, vector(__VA_ARGS__)))) struct RandGen { using ud = uniform_int_distribution; mt19937 mt; RandGen() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} ll l(ll a, ll b) { ud d(a, b - 1); return d(mt); } LP lp(ll a, ll b, bool rng = true) { ll x = l(a, b - 1), y = l(rng ? x + 1 : a, b - 1); return {x, y}; } vl vecl(ll n, ll a, ll b) { ud d(a, b - 1); vl ret(n); rep(i, n) ret[i] = d(mt); return ret; } vl vecperm(ll n, ll from = 0) { vl perm(n); iota(all(perm), from); shuffle(perm); return perm; } string str(ll n, string op) { vl fig = vecl(n, 0, op.size()); string s; rep(i, n) s.pb(op[fig[i]]); return s; } string straz(ll n, ll a = 0, ll z = 26) { vl az = vecl(n, a, z); string s; rep(i, n) s.pb('a' + az[i]); return s; } string strnum(ll n, ll zero = 0, ll ten = 10) { vl zt = vecl(n, zero, ten); string s; rep(i, n) s.pb('0' + zt[i]); return s; } template void shuffle(vector &a) { std::shuffle(all(a), mt); } }; // 入出力マクロの上に #include #include using namespace atcoder; using mint = modint998244353; using vmi = vector; using vvmi = vector; using v3mi = vector; using v4mi = vector; const ll mod = 998244353; istream& operator>>(istream& in, mint a) { long long e; in >> e; a = e; return in; } ostream& operator<<(ostream& out, mint a) { return out << a.val(); } template istream &operator>>(istream &is, vector &v) { for (auto &e : v) is >> const_cast(e); return is; } template ostream &operator<<(ostream &os, const vector &v) { for (auto &e : v) os << const_cast(e) << ' '; return os; } //------------------------------------------------------------------------------ // デバッグ系 #define dout cout template struct is_specialize:false_type{}; template struct is_specialize::type>:true_type{}; template struct is_specialize::type>:true_type{}; template struct is_specialize::value, void>>:true_type{}; void dump(const char &t) { dout<::value, nullptr_t> =nullptr> void dump(const T&t) { dout << const_cast(t); } template void dump(const T&t, enable_if_t::value>* =nullptr) { string tmp;if(t==infinity::val||t==infinity::MAX)tmp="inf";if(is_signed::value&&(t==infinity::mval||t==infinity::MIN))tmp="-inf";if(tmp.empty())tmp=to_string(t);dout< void dump(const tuple&t) { dout<<"("; dump(get<0>(t)); dout<<" "; dump(get<1>(t)); dout << " "; dump(get<2>(t)); dout << ")"; } template void dump(const tuple&t) { dout<<"("; dump(get<0>(t)); dout<<" "; dump(get<1>(t)); dout << " "; dump(get<2>(t)); dout << " "; dump(get<3>(t)); dout << ")"; } template void dump(const pair&); template void dump(const T&t, enable_if_t::value>* =nullptr) { dout << "{ "; for(auto it=t.begin();it!=t.end();){ dump(*it); dout << (++it==t.end() ? "" : " "); } dout<<" }"; } template void dump(const pair&t) { dout<<"("; dump(t.first); dout<<" "; dump(t.second); dout << ")"; } void trace() { dout << "\n"; } template void trace(Head&&head, Tail&&... tail) { dump(head); if(sizeof...(tail)) dout<<", "; trace(forward(tail)...); } #ifdef ONLINE_JUDGE #define debug(...) (void(0)) #else #define debug(...) do {dout<<#__VA_ARGS__<<" = ";trace(__VA_ARGS__); } while(0) #endif // 入出力系 #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; IN(__VA_ARGS__) #define _vl(name, size) vl name(size); IN(name) #define _vl2(name, size, off) vl name(size); IN(name); rep(i, size) name[i]-=off #define VL(...) _overload3(__VA_ARGS__, _vl2, _vl)(__VA_ARGS__) #define VEC(type, name, size) vector name(size); IN(name) #define VEC2(type, name1, name2, size) vector name1(size), name2(size); for(int i = 0; i < size; i++) IN(name1[i], name2[i]) #define VEC3(type, name1, name2, name3, size) vector name1(size), name2(size), name3(size); for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i]) #define VEC4(type, name1, name2, name3, name4, size) vector name1(size), name2(size), name3(size), name4(size); for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]); #define VV(type, name, h, w) vector> name(h, vector(w)); IN(name) void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(string &a) { cin >> a; } template void scan(T &a) { cin >> a; } template void scan(pair &p) { scan(p.first), scan(p.second); } template void scan(vector &a) { for(auto &i : a) scan(i); } void IN() {} template void IN(Head &head, Tail &...tail) { scan(head); IN(tail...); } #define OUTRET(...) { { OUT(__VA_ARGS__); return; } } #define YES(ok) { if (ok) { OUT("YES"); } else OUT("NO"); } #define Yes(ok) { if (ok) { OUT("Yes"); } else OUT("No"); } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << " " << p.second; } void OUT() { cout << '\n'; } template void OUT(const Head &head, const Tail &...tail) { cout << head; if(sizeof...(tail)) cout << ' '; OUT(tail...); } template void OUTARRAY(vector& v, S offset = S(0), string sep = " ") { rep(i, v.size()) { if (i > 0) cout << sep; if (offset != T(0)) { T t; t = v[i] + offset; cout << t; } else cout << v[i]; } cout << "\n"; } template void OUTMAT(vector>& v, S offset = S(0)) { rep(i, v.size()) { OUTARRAY(v[i], offset); } } template void OUTBIN(T &a, int d) { for (int i = d - 1; i >= 0; i--) cout << ((a >> i) & (T)1); cout << "\n"; } template void IQUERY(initializer_list q, A &a, string str = "? ") { cout << str; vector v(q); OUTARRAY(v); cout.flush(); cin >> a; } // template void IQUERY(initializer_list q, A &a, string str = "? ") { vector query(q); RandGen rg; // a = query[0] ? A() : A(); // } template void IANSWER(initializer_list a, string str = "! ") { cout << str; vector v(a); OUTARRAY(v); cout.flush(); } // 数値系 int ceil_pow2(ll n) { int x = 0; while ((1ULL << x) < (ull)(n)) x++; return x; } int floor_pow2(ll n) { int x = 0; while ((1ULL << (x + 1)) <= (ull)(n)) x++; return x; } pair sqrtll(ll n) { ll x = round(sqrt(n)); if (x * x > n) --x; return {x, x + (x * x != n)}; } ll POW(__uint128_t x, int n) { assert(n >= 0); ll res = 1; for(; n; n >>= 1, x *= x) if(n & 1) res *= x; return res; } vl primes(const ll n) { vb isp(n + 1, true); for(ll i = 2; i * i <= n; i++) { if ((i > 2 && i % 2 == 0) || !isp[i]) continue; for(ll j = i * i; j <= n; j += i) isp[j] = 0; } vl ret; for(ll i = 2; i <= n; i++) if (isp[i]) ret.emplace_back(i); return ret; } vector> factorize(ll n) { vector> res; for (ll a = 2; a * a <= n; ++a) { if (n % a != 0) continue; ll ex = 0; while (n % a == 0) { ++ex; n /= a; } res.emplace_back(a, ex); } if (n != 1) res.emplace_back(n, 1); return res; } vl divisor(ll n) { vl ret; for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.pb(i); if (i * i != n) ret.pb(n / i); } } sort(all(ret)); return ret; } template vl digits(T n) { assert(n >= 0); vl ret; while(n > 0) { ret.pb(n % 10); n /= 10; } return ret; } template::value, nullptr_t> = nullptr> int msb(T x){ if (sizeof(x) == 4) return 31 - __builtin_clz(x); else return 63 - __builtin_clzll(x); } template::value, nullptr_t> = nullptr> int lsb(T x){ if (sizeof(x) == 4) return __builtin_ctz(x); else return __builtin_ctzll(x); } template T ceil(T x, S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template T floor(T x, S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : (x - y + 1) / y)); } template T sum_of(const vector &v, int l = 0, int r = INF) { return accumulate(rng_of(v, l, min(r, (int)v.size())), T(0)); } template constexpr auto min(T... a){ return min(initializer_list>{a...}); } template constexpr auto mine(T... a) { return min(a..., LINF, LINF); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } template constexpr auto maxe(T... a) { return max(a..., -LINF, -LINF); } ll mex(vl& v) { ll n = v.size(); vb S(n + 1); for (auto a: v) if (a <= n) S[a] = 1; ll ret = 0; while (S[ret]) ret++; return ret; } // 操作系 template void rotate(vector> &a) { ll n = a.size(), m = a[0].size(); vector> ret(m, vector(n, 0)); rep(i, n) rep(j, m) ret[j][n - 1 - i] = a[i][j]; a = ret; } template void uniq(vector&a) { sort(all(a)); a.erase(unique(all(a)), a.end()); } template void comp(vector&a) { vector b = a; uniq(b); rep(i, a.size()) a[i] = lower_bound(all(b), a[i]) - b.begin(); } template pair, unordered_map> compmap(vector &a) { vector ca = a; comp(ca); unordered_map ret, rev; rep(i, ca.size()) { ret[a[i]] = ca[i]; rev[ca[i]] = a[i]; } return mp(ret, rev); } template bool chmin(T &a, const U &b) { if (b < a) { a = b; return 1;} return 0; } template bool chmax(T &a, const U &b) { if (b > a) { a = b; return 1;} return 0; } template int lbs(vector &a, const T &b) { return lower_bound(all(a), b) - a.begin(); }; template int ubs(vector &a, const T &b) { return upper_bound(all(a), b) - a.begin(); }; ll binary_search(function check, ll ok, ll ng, bool safe=true) { if (safe) { assert(check(ok)); assert(!check(ng)); } while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; } template vector csum(vector &a) { vector ret(a.size() + 1, 0); rep(i, a.size()) ret[i + 1] = ret[i] + a[i]; return ret; } template vector argsort(const vector &a) { vector ids(a.size()); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return a[i] == a[j] ? i < j : a[i] < a[j]; }); return ids; } template vector rearrange(const vector &orig, const vector &rep) { assert(orig.size() == rep.size()); ll n = rep.size(); vector ret(n); rep(i, n) ret[i] = orig[rep[i]]; return ret; } template vector> RLE(const vector &v) { vector> res; for(auto &e : v) if(res.empty() or res.back().first != e) res.emplace_back(e, 1); else res.back().second++; return res; } vector> RLE(const string &v) { vector> res; for(auto &e : v) if(res.empty() or res.back().first != e) res.emplace_back(e, 1); else res.back().second++; return res; } template bool incl(const T &x, const S &l, const U &r) { return l <= x and x < r; } void change_bit(ll &x, int b, int i) { assert(b < 63); if (!!(x & 1ll << b) ^ i) x ^= 1ll << b; } bool is_palindrome(string s) { rep(i, (s.size() + 1) / 2) if (s[i] != s[s.size() - 1 - i]) { return false; } return true; } // グラフ系 template< typename T = ll > struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } bool operator<(const struct Edge& other) const { return cost < other.cost; } }; template< typename T = ll > struct Graph { vector< vector< Edge< T > > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } inline vector< Edge< T > > &operator[](const int &k) { return g[k]; } inline const vector< Edge< T > > &operator[](const int &k) const { return g[k]; } }; const string drul = "DRUL"; const vl dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; ll solve(ll n, vl a) { ll ans = n - a[0]; return ans; } ll naive(ll n, vl a) { ll ans = n + a[0]; return ans; } void compare(bool check = true) { RandGen rg; ll c = 0, loop = 10; while (++c) { if (c % loop == 0) cout << "reached " << c / loop << "loop" << "\n", cout.flush(); ll n = 10; vl a = rg.vecl(n, 1, 1e2); auto so = solve(n, a); auto na = naive(n, a); if (!check || na != so) { cout << c << "times tried" << "\n"; debug(n, a); debug(so); debug(na); if (check || (!check && c > loop)) break; } } } const int max_n = (1 << 20) + 1; mint fact[max_n], factinv[max_n]; void init_f() { fact[0] = 1; for (int i = 0; i < max_n - 1; i++) { fact[i + 1] = fact[i] * (i + 1); } factinv[max_n - 1] = mint(1) / fact[max_n - 1]; for (int i = max_n - 2; i >= 0; i--) { factinv[i] = factinv[i + 1] * (i + 1); } } mint comb(int a, int b) { assert(a < max_n && fact[0] != 0); if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[b] * factinv[a - b]; } mint combP(int a, int b) { assert(a < max_n && fact[0] != 0); if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[a - b]; } //------------------------------------------------------------------------------ // Nlog^2Nで複数配列を効率よくたたみ込むもの vmi all_convolution(vvmi &a) { multimap que; for (auto &v: a) que.emplace(v.size(), v); while (que.size() > 1) { vmi a = que.begin()->se; que.erase(que.begin()); vmi b = que.begin()->se; que.erase(que.begin()); vmi c = convolution(a, b); que.emplace(c.size(), c); } return que.begin()->se; } //------------------------------------------------------------------------------ template struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector(n, e())) {} explicit segtree(const std::vector& v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) update(i); } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; //------------------------------------------------------------------------------ ll k; using S = vmi; S op(S l, S r) { auto ret = convolution(l, r); rep(i, k, ret.size()) { ret[i % k] += ret[i]; } ret.resize(k); return ret; } S e() { return {1}; } void solve() { LL(n, m); IN(k); VL(a, n); vvmi v; rep(i, n) { vmi t(a[i] % k + 1); t[0] += 1; t[a[i] % k] += 1; v.pb(t); } // debug(v); segtree seg(v); rep(i, n - m + 1) { // debug(seg.prod(i, i + m)); OUT(seg.prod(i, i + m)[0] - 1); } } signed main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(20); int t = 1; // cin >> t; while (t--) if (1) solve(); else compare(); }