You need to construct a string s of length n consisting of lowercase English letters (from "a
" to "z
") that is not scared.
Let a string s be scared if there is at least one character in the string that sees more than 20 characters that are greater than or equal to it.
We define a character a to be greater than character b if character a comes after character b in the alphabet. For example, "f
" > "b
". Also, if character a is greater than character b, then we define b to be smaller than a (for example, "b
" < "f
").
We say that the character at position i sees the character at position j if j<i and there is no index k (j<k<i) such that sk is greater than sj.
For example, in the string "abacc
", the "a
" at position 3 does not see the "a
" at position 1 because between them there is "b
" which is greater than the "a
" at position 1. But the "c
" at position 4 can see the "b
" at position 2 because between them the greatest character is "a
" which is not greater than the "b
" at position 2.
The only line contains a single integer n (1≤n≤105) — the size of the string which you need to construct.
In the only line, you need to output the string of length n which is not scared and consists only of lowercase English letters.
In the first test case, the string "anton
" is not scared because no character sees more than 20 characters that are greater than or equal to it:
the first character "a
" does not see anything;
the second character "n
" sees only "a
" but it is smaller than "n
";
the third character "t
" sees "n
", but it is smaller than "t
";
the fourth character "o
" sees only "t
";
the fifth character "n
" sees "t
" and "o
" that are greater than s5= "n
", but there are only 2 such characters, which is less than 20.
Also, notice that in the third test case, in the string "aabbaa
", the 6-th character "a
" sees both "b
"'s at the 3-rd and at the 4-th positions since there are no characters between the 3-rd and the 6-th ones which are greater than "b
".
(52 points): n≤400;
(86 points): n≤8000;
(162 points): no additional constraints.