Algorithm

B. K-th Beautiful String time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output For the given integer  n n  ( n > 2 n > 2 ) let's write down all the strings of length  n n  which contain  n − 2 n − 2  letters ' a ' and two letters ' b ' in  lexicographical  (alphabetical) order. Recall that the string  s s  of length  n n  is lexicographically less than string  t t  of length  n n , if there exists such  i i  ( 1 ≤ i ≤ n 1 ≤ i ≤ n ), that  s i < t i s i < t i , and for any  j j  ( 1 ≤ j < i 1 ≤ j < i )  s j = t j s j = t j . The lexicographic comparison of strings is implemented by the operator  <  in modern programming languages. For example, if  n = 5 n = 5  the strings are (the order does matter): aaabb aabab aabba abaab ababa abbaa baaab baaba babaa bbaaa It is easy to show that such a list of strings will contain exactly  n ⋅ ( n − 1 ) 2 n ⋅ ( n