#line 1 "e.cpp" #include using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using pq_ = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;} template T square(T a){return a * a;} #line 6 "/Users/Shared/po167_library/string/Trie_Tree.hpp" namespace po167{ template struct Trie_Tree { struct Node{ std::array next_node; std::vector terminate_node; int parent_node; int char_number; int accepet_count; explicit Node(int c_):parent_node(-1),char_number(c_),accepet_count(0){ for(int i=0;i nodes; std::vector fail; Trie_Tree(){ nodes.push_back(Node(-1)); } std::vector insert(std::string &word,int word_id){ int node_id=0; std::vector ids; for (char & i : word){ node_id=min_insert(i,node_id,word_id); ids.push_back(node_id); } nodes[ids.back()].terminate_node.push_back(word_id); return ids; } int min_insert(char ch,int node_id,int word_id){ int c=(int)(ch-base); int next_id=nodes[node_id].next_node[c]; if(next_id==-1){ next_id=(int)nodes.size(); nodes.push_back(Node(c)); } nodes[next_id].parent_node=node_id; nodes[node_id].next_node[c]=next_id; // nodes[next_id].accept_node.push_back(word_id); nodes[node_id].accepet_count++; node_id=next_id; return node_id; } void aho(){ fail.resize(nodes.size()); std::vector order = {0}; order.reserve(nodes.size()); for (int i = 0; i < (int)(order.size()); i++){ int id = order[i]; if (id == 0){ fail[id] = 0; } else{ int f = fail[nodes[id].parent_node]; int c = nodes[id].char_number; while (f != fail[f] && nodes[f].next_node[c] == -1){ f = fail[f]; } if (nodes[f].next_node[c] != -1 && nodes[f].next_node[c] != id) fail[id] = nodes[f].next_node[c]; else fail[id] = 0; } for (int j = 0; j < char_size; j++){ if (nodes[id].next_node[j] != -1) order.push_back(nodes[id].next_node[j]); } } } // node であって、追加した文字列を部分列として含まないものを返す // aho を呼んでいないなら呼びます std::vector taboo(){ if (fail.size() != nodes.size()){ aho(); } std::vector order = {0}; std::vector taboo(nodes.size(), false); for (int i = 0; i < (int)order.size(); i++){ int a = order[i]; if (!nodes[a].terminate_node.empty()) taboo[a] = true; if (taboo[fail[a]]) taboo[a] = true; if (a != 0 && taboo[nodes[a].parent_node]) taboo[a] = true; for (int j = 0; j < char_size; j++){ int c = nodes[a].next_node[j]; if (c != -1) order.push_back(c); } } return taboo; } }; } using po167::Trie_Tree; #line 26 "e.cpp" void solve(); // DEAR MYSTERIES / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ int N, M; cin >> N >> M; Trie_Tree<26, 'a'> T; rep(i, 0, N) { string S; cin >> S; T.insert(S, i); } int ans = 0; int rem = N; string X, Y; auto f = [&](auto self, int a) -> void { if (ans + rem < M) return; rep(i, 0, 26) { if (!Y.empty()) break; int ok = 0, nx = -1; if (T.nodes[a].next_node[i] == -1) { ok = 1; } else { nx = T.nodes[a].next_node[i]; // cout << nx << " " << T.nodes[nx].accepet_count << "" << T.nodes[nx].terminate_node.size() << "\n"; if (ans + rem - T.nodes[nx].accepet_count - T.nodes[nx].terminate_node.size() >= M) { ok = 1; } } if (ok) { Y = X; Y += (char)('a' + i); break; } else { X += (char)('a' + i); int s_ans = ans; int s_rem = rem; ans += rem - T.nodes[nx].accepet_count - T.nodes[nx].terminate_node.size(); rem = T.nodes[nx].accepet_count; self(self, nx); ans = s_ans; rem = s_rem; } } }; f(f, 0); if (yneos(!Y.empty())) { cout << Y << "\n"; } }