/** * date : 2021-12-02 00:54:12 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template inline T Max(const vector &v) { return *max_element(begin(v), end(v)); } template inline T Min(const vector &v) { return *min_element(begin(v), end(v)); } template inline long long Sum(const vector &v) { return accumulate(begin(v), end(v), 0LL); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkinv(vector &v) { int max_val = *max_element(begin(v), end(v)); vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { if (gbit(a, i) != b) a ^= T(1) << i; } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } void dump(const bool& t) { cerr << (t ? "true" : "false"); } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::inf) res = "-inf"; } if constexpr (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::infLL) res = "-inf"; } } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) (void(0)) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define fi first #define se second #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } // // reference : http://www.ivis.co.jp/text/20111102.pdf struct SurrealNumber { using S = SurrealNumber; using i64 = long long; // p / 2^q の形で保持 i64 p, q; SurrealNumber(i64 _p = 0, i64 _q = 0) : p(_p), q(_q) {} friend ostream& operator<<(ostream& os, const SurrealNumber& r) { os << r.p; if (r.q != 0) os << " / " << (i64{1} << r.q); return os; } static S normalize(S s) { if (s.p != 0) { while (s.p % 2 == 0 and s.q != 0) s.p /= 2, s.q--; } else { s.q = 0; } return {s.p, s.q}; } // 加算・減算 friend S operator+(const S& l, const S& r) { i64 cq = max(l.q, r.q); i64 cp = (l.p << (cq - l.q)) + (r.p << (cq - r.q)); return normalize(S{cp, cq}); } friend S operator-(const S& l, const S& r) { i64 cq = max(l.q, r.q); i64 cp = (l.p << (cq - l.q)) - (r.p << (cq - r.q)); return normalize(S{cp, cq}); } S& operator+=(const S& r) { return (*this) = (*this) + r; } S& operator-=(const S& r) { return (*this) = (*this) - r; } // 大小関係 friend bool operator<(const S& l, const S& r) { return (r - l).p > 0; } friend bool operator<=(const S& l, const S& r) { return (r - l).p >= 0; } friend bool operator>(const S& l, const S& r) { return (l - r).p > 0; } friend bool operator>=(const S& l, const S& r) { return (l - r).p >= 0; } friend bool operator==(const S& l, const S& r) { return (l - r).p == 0; } friend bool operator!=(const S& l, const S& r) { return (l - r).p != 0; } // 左右の子を返す関数 pair child() const { if (p == 0) return {-1, 1}; if (q == 0 and p > 0) return {S{p * 2 - 1, 1}, p + 1}; if (q == 0 and p < 0) return {p - 1, S{p * 2 + 1, 1}}; return {(*this) - S{1, q + 1}, (*this) + S{1, q + 1}}; } S larger() const { S root = 0; while ((*this) >= root) root = root.child().second; return root; } S smaller() const { S root = 0; while ((*this) <= root) root = root.child().first; return root; } friend S reduce(const S& l, const S& r) { assert(l < r); S root = 0; while (l >= root or root >= r) { auto [lr, rr] = root.child(); root = (r <= root ? lr : rr); } return root; } }; template struct PartisanGame { using Games = vector; using S = SurrealNumber; map mp; F f; PartisanGame(const F& _f) : f(_f) {} S zero() const { return S{0}; } S get(Game g) { if (mp.count(g)) return mp[g]; return mp[g] = _get(g); } private: S _get(Game g) { Games gl, gr; tie(gl, gr) = f(g); if (gl.empty() and gr.empty()) return 0; vector l, r; for (auto& cg : gl) l.push_back(get(cg)); for (auto& cg : gr) r.push_back(get(cg)); S sl, sr; if (!l.empty()) sl = *max_element(begin(l), end(l)); if (!r.empty()) sr = *min_element(begin(r), end(r)); if (r.empty()) return sl.larger(); if (l.empty()) return sr.smaller(); assert(sl < sr); return reduce(sl, sr); } }; template struct ImpartialGame { using Games = vector; using N = long long; map mp; F f; ImpartialGame(const F& _f) : f(_f) {} N zero() const { return N{0}; } N get(Game g) { if (mp.count(g)) return mp[g]; return mp[g] = _get(g); } private: N _get(Game g) { Games gs = f(g); if (gs.empty()) return 0; vector ns; for (auto& cg : gs) ns.push_back(get(cg)); sort(begin(ns), end(ns)); ns.erase(unique(begin(ns), end(ns)), end(ns)); for (int i = 0; i < (int)ns.size(); i++) { if (ns[i] != i) return i; } return (int)ns.size(); } }; using namespace Nyaan; void test(int n, int K) { auto f = [&n, &K](vi v) { vvi res; int s = v[0], pre = v[1]; for (int i = 1; i <= K; i++) { if (pre != i and i + s < n) { res.push_back(vi{s + i, i}); } } return res; }; ImpartialGame game{f}; vi start{0, 0}; game.get(start); // trc(K, n, game.get(start)); for (int i = 0; i < n; i++) { cerr << setw(2) << i << " : "; for (int j = 0; j <= K; j++) { cerr << game.get(vi{i, j}) << " "; } cerr << endl; } } // LazySegmentTree template struct LazySegmentTree { int n, height; F f; G g; H h; T ti; E ei; vector dat; vector laz; LazySegmentTree(int _n, F _f, G _g, H _h, T _ti, E _ei) : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) { init(_n); } LazySegmentTree(const vector &v, F _f, G _g, H _h, T _ti, E _ei) : f(_f), g(_g), h(_h), ti(_ti), ei(_ei) { init((int)v.size()); build(v); } void init(int _n) { n = 1; height = 0; while (n < _n) n <<= 1, height++; dat.assign(2 * n, ti); laz.assign(2 * n, ei); } void build(const vector &v) { int _n = v.size(); init(_n); for (int i = 0; i < _n; i++) dat[n + i] = v[i]; for (int i = n - 1; i; i--) dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]); } inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); } inline void eval(int k) { if (laz[k] == ei) return; laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]); laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]); dat[k] = reflect(k); laz[k] = ei; } inline void thrust(int k) { for (int i = height; i; i--) eval(k >> i); } inline void recalc(int k) { while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1)); } void update(int a, int b, E x) { if (a >= b) return; thrust(a += n); thrust(b += n - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) laz[l] = h(laz[l], x), l++; if (r & 1) --r, laz[r] = h(laz[r], x); } recalc(a); recalc(b); } void set_val(int a, T x) { thrust(a += n); dat[a] = x; laz[a] = ei; recalc(a); } T get_val(int a) { thrust(a += n); return reflect(a); } T query(int a, int b) { if (a >= b) return ti; thrust(a += n); thrust(b += n - 1); T vl = ti, vr = ti; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) vl = f(vl, reflect(l++)); if (r & 1) vr = f(reflect(--r), vr); } return f(vl, vr); } }; void Nyaan::solve() { // test(60, 10); inl(N, K); vi ans; auto f = [](pl a, pl b) { return a + b; }; LazySegmentTree seg(vp(N + 1), f, f, f, pl{0, 0}, pl{0, 0}); for (int i = N - 1; i >= 1; i--) { auto p = seg.get_val(i); trc(i,p); if (p.fi == 0) { // all 0 seg.update(max(0, i - K), i, pl{1, i}); if (i <= K) ans.push_back(i); } else if (p.fi == 1) { int last = p.se; // (i, exc) のみ 0 int j = last - i; // (i, j) のみ 0 if (i == j and i <= K) ans.push_back(i); if (i - j >= 0) seg.update(i - j, i - j + 1, pl{1, i}); } } sort(all(ans)); each(x,ans) out(x); }