{"raw_statement":[{"iden":"statement","content":"Sometimes, in string problems you have to find a string satisfying some conditions. The authors again were too lazy to think of a tricky term for such string, so they called it _good_.\n\nA string is called good if it contains exactly k different characters. You are given a string s. Find the minimal number of good strings so that their concatenation is s.\n\nThe first line contains an integer k (1 ≤ k ≤ 26).\n\nThe second line contains a string s (1 ≤ |s| ≤ 200000), consisting of lowercase Latin letters.\n\nFor every prefix of s, starting from the prefix consisting of the first character of s, and ending with s itself, output the minimal number of good strings so that their concatenation is this prefix. Solutions will be tested more carefully this way, won't they?\n\nIf for some prefix the decomposition into good strings isn't possible, output «_-1_» for it.\n\n"},{"iden":"input","content":"The first line contains an integer k (1 ≤ k ≤ 26).The second line contains a string s (1 ≤ |s| ≤ 200000), consisting of lowercase Latin letters."},{"iden":"output","content":"For every prefix of s, starting from the prefix consisting of the first character of s, and ending with s itself, output the minimal number of good strings so that their concatenation is this prefix. Solutions will be tested more carefully this way, won't they?If for some prefix the decomposition into good strings isn't possible, output «_-1_» for it."},{"iden":"examples","content":"Input2abacabaOutput-1 1 1 2 2 3 3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 26 $.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n = |s| $, where $ s_i \\in \\{a, b, \\dots, z\\} $.  \nA string is *good* if it contains exactly $ k $ distinct characters.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 200000 $\n\n**Objective**  \nFor each prefix $ s[1..i] $ (for $ i = 1 $ to $ n $), compute the minimal number $ m_i $ of good strings whose concatenation equals $ s[1..i] $.  \nIf no such decomposition exists, set $ m_i = -1 $.  \n\nOutput $ m_1, m_2, \\dots, m_n $.","simple_statement":"Given a string s and an integer k, for each prefix of s, find the minimum number of substrings (called \"good\") needed to form that prefix, where each good substring contains exactly k distinct characters. If impossible, output -1.","has_page_source":false}