// #pragma GCC target("avx") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; #define rep(i,n) for(int i = 0; i < (int)n; i++) #define FOR(n) for(int i = 0; i < (int)n; i++) #define repi(i,a,b) for(int i = (int)a; i < (int)b; i++) #define all(x) x.begin(),x.end() //#define mp make_pair #define vi vector #define vvi vector #define vvvi vector #define vvvvi vector #define pii pair #define vpii vector> template void chmax(T &a, const T &b) {a = (a > b? a : b);} template void chmin(T &a, const T &b) {a = (a < b? a : b);} using ll = long long; using ld = long double; const ll INF = numeric_limits::max() / 2; const ld pi = 3.1415926535897932384626433832795028; const ll mod = 998244353; int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}; int dy[] = {0, -1, 0, 1, -1, 1, -1, 1}; using ull = unsigned long long; struct Rolling_Hash { static const unsigned long long rh_mod = (1ull << 61ull) - 1; vector power; unsigned long long base; static inline unsigned long long add(unsigned long long a, unsigned long long b) { if((a += b) >= rh_mod) a -= rh_mod; return a; } static inline unsigned long long mul(unsigned long long a, unsigned long long b) { __uint128_t c = (__uint128_t) a * b; return add(c >> 61, c & rh_mod); } static inline unsigned long long generate_base() { mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution< unsigned long long > rand(1, Rolling_Hash::rh_mod - 1); return rand(mt); } inline void expand(size_t sz) { if((int)power.size() < (int)sz + 1) { int pre_sz = (int) power.size(); power.resize(sz + 1); for(int i = pre_sz - 1; i < (int)sz; i++) { power[i + 1] = mul(power[i], base); } } } Rolling_Hash() { base = generate_base(); power = {1}; } vector make_hash(const string &s) const { int sz = s.size(); vector hashed(sz + 1); for(int i = 0; i < (int)sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } template vector make_hash(const vector &s) const { int sz = s.size(); vector hashed(sz + 1); for(int i = 0; i < (int)sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } vector make_hash_string(const string &s) const { vector ss; for(char c : s) ss.push_back(c); return make_hash(ss); } unsigned long long query(const vector &s, int l, int r) { expand(r - l); return add(s[r], rh_mod - mul(s[l], power[r - l])); } unsigned long long combine(unsigned long long h1, unsigned long long h2, size_t h2len) { expand(h2len); return add(mul(h1, power[h2len]), h2); } int lcp(const vector &a, int l1, int r1, const vector &b, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = 0, high = len + 1; while(high - low > 1) { int mid = (low + high) / 2; if(query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid; else high = mid; } return low; } bool issame(const vector &a, int l1, int r1, const vector &b, int l2, int r2) { assert(r1-l1 == r2-l2); return query(a, l1, r1) == query(b, l2, r2); } bool issame(const vector &a, int l1, const vector &b, int l2, int len) { return issame(a, l1, l1+len, b, l2, l2+len); } template int greater(const vector &raw, const vector &hash, int l1, int r1, int l2, int r2) { // repi(i, l1, r1) cout << raw[i]; cout << " "; // repi(i, l2, r2) cout << raw[i]; cout << "\n"; int LCP = lcp(hash, l1, r1, hash, l2, r2); if(LCP == min(r1 - l1, r2 - l2)) return 2;//same //0: l1の方がでかい, 1: l2の方がでかい return raw[l1+LCP] < raw[l2+LCP]; } }; //make function that can combine two hash tables //combine_hashes(vull l, vull r) -> return vull l+r (hash addition) void solve() { Rolling_Hash rh; int n, k; cin >> n >> k; vi s(n); FOR(n) cin >> s[i]; vector hash = rh.make_hash(s); vector ans(n); iota(all(ans), 0); sort(all(ans), [&](int i, int j) { int now; // cout << i << " " << j << endl; if(i < j) { now = rh.greater(s, hash, i+1, j+1, i, j); }else { now = rh.greater(s, hash, j, i, j+1, i+1); } // cout << now << endl; if(now == 2) { return false; } if(now == 1) { return true; } if(now == 0) { return false; } assert(false); return false; }); FOR(n) if(i != ans[k-1]) cout << s[i] << " "; cout << "\n"; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }