// 提出時にassertはオフ #ifndef DEBUG #ifndef NDEBUG #define NDEBUG #endif #endif #include using namespace std; using ll = long long; #define all(x) (x).begin(), (x).end() template using vec = vector; struct rollhash_mod { public: // [2, MOD - 2]のbaseを乱数として生成 static ll genBase() { random_device seed; // 非決定的な乱数 mt19937_64 mt(seed()); // メルセンヌ・ツイスタ 64bit uniform_int_distribution randbase(2LL, MOD - 2); return randbase(mt); } // べき乗のmod(tableを用意せずその場でやってるのでlog(beki)かかる) constexpr static ll power(ll base, ll beki) { rollhash_mod curbekiMod(base); rollhash_mod ret(1); while(beki > 0) { if(beki & 1) ret *= curbekiMod; curbekiMod *= curbekiMod; beki >>= 1; } return ret.val(); } constexpr rollhash_mod(ll x = 0) : value(calcMod(x)) {} constexpr ll val() const { return value; } constexpr rollhash_mod &operator+=(const rollhash_mod &a) { if((value += a.value) >= MOD) value -= MOD; return *this; } constexpr rollhash_mod &operator-=(const rollhash_mod &a) { *this += (MOD - a.value); return *this; } constexpr rollhash_mod &operator*=(const rollhash_mod &a) { value = ((__int128_t)value * a.value) % MOD; return *this; } constexpr rollhash_mod operator+(const rollhash_mod &a) { rollhash_mod cpy(*this); return cpy += a; } constexpr rollhash_mod operator-(const rollhash_mod &a) { rollhash_mod cpy(*this); return cpy -= a; } constexpr rollhash_mod operator*(const rollhash_mod &a) { rollhash_mod cpy(*this); return cpy *= a; } constexpr bool operator==(const rollhash_mod & a){ return value == a.value; } private: ll value; // 中で保持しておくmod constexpr static ll MOD = (1LL << 61) - 1; constexpr static ll calcMod(const ll &x) { ll cur = x >> 61; if((cur += (x & MOD)) >= MOD) cur -= MOD; return cur; } }; int N, K; vec A; // beki_table[i] = beki^i vec basebeki_table; // [0, i) vec front_table; // X_iの先頭k文字の接頭辞 rollhash_mod X_i_prefix(int i, int k) { assert(0 <= i && i <= N - 1); assert(0 <= k && k <= N - 1); if(i >= k) return front_table[k]; rollhash_mod latter = front_table[k + 1] - front_table[i + 1] * basebeki_table[k - i]; rollhash_mod former = front_table[i] * basebeki_table[k - i]; return latter + former; } // X_iとX_jの共通接頭辞の長さを二分探索で求める int prefix_len(int i, int j){ int l = 0, r = N; while(r - l > 1){ int m = (l + r) / 2; if(X_i_prefix(i, m) == X_i_prefix(j, m)) l = m; else r = m; } return l; } // X_iとX_jのうち辞書順でiが小さければtrue bool dict_cmp(int i, int j){ int len = prefix_len(i, j); // 完全一致 if(len == N - 1) return false; auto getcmpnum = [&] (int i) -> int { if(i == 0) return A[len + 1]; if(i == N - 1) return A[len]; // 0,..,i-1,i+1,...,N-1 if(len <= i - 1) return A[len]; else return A[len + 1]; }; return getcmpnum(i) < getcmpnum(j); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; A = vec(N); for(int &a : A) cin >> a; // baseのべきのtableを予め作る ll base = rollhash_mod::genBase(); basebeki_table = vec(N + 1, 1); for(int i = 1; i <= N; ++i) { basebeki_table[i] = basebeki_table[i - 1] * base; } // Aの接頭辞[0,i)のmodを求めておく front_table = vec(N + 1, 0); for(int i = 1; i <= N; ++i) { front_table[i] = front_table[i - 1] * base + A[i - 1]; } vec permu(N); for(int i = 0; i < N; ++i){ permu[i] = i; } sort(all(permu), dict_cmp); #ifdef DEBUG for(int i = 0; i < N; i++){ int ansIndex = permu[i]; cout << ansIndex << ": "; for(int j = 0; j < N; j++){ if(j != ansIndex) cout << A[j] << " "; } cout << "\n"; } #endif int ansIndex = permu[K - 1]; for(int i = 0; i < N; i++){ if(i != ansIndex) cout << A[i] << " "; } cout << "\n"; }