Polish version    English version  
  History of OI -> X OI 2002/2003


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003

Problem: Sequences without Stammers
Author: Krzysztof Sikora

We consider sequences of letters. We say a sequence x1x2...xn contains a stammer, if we can find in it two occurrences of the same subsequence, one directly following the other, i.e. if for some i and j (1 <= i < j <= (n+i+1)/2) we have xi = xj, xi+1 = xj+1, ..., xj-1 = x2j-i-1.

We are interested in n-element sequences having no stammers, built of the minimal number of different letters.

Example

For n = 3 it is enough to use two letters, say a and b. We have exactly two 3-element sequences without stammers build of those letters: aba and bab. For n = 5 we need three different letters. For example abcab is a three-letter sequence without stammers. In the sequence babab we have two stammers: ba and ab.

Task

Write a program which:
  • reads the length of the sequence n,
  • computes an n-element sequence with no stammers built of the minimal number of different letters,
  • writes the result.

Input

In the first line of the standard input there is one positive integer n, 1 <= n <= 10000000.

Output

Your program should write to the standard output. In the first line there should be one positive integer k equal to the minimal number of different letters that must appear in an n-element sequence having no stammers.

In the second line one should write the computed sequence without stammers as a word that comprises n lower case letters of English alphabet and is built only of the letters from a up to the k-th letter of the alphabet. If there are many such sequences, your program should write one of them.

You may assume 26 letters are enough.

Example

For the following input data:
5
a correct answer is in the following output:
3
abcab



Print friendly version