#2606. [Poi2003] Sequences without Stammers

题目描述

我们考虑一个字符序列. 如果 x 1 x 2... x n 包含一个 stammer , 当且仅当我们能在里面找到两个相同的连续的子串。即存在 i 和 j (1 <= i < j <= ( n + i +1)/2) ，其中 x i = x j, x i+1 = x j+1, ..., x j-1 = x 2 j - i -1.

我们想找出一个长度为 n 的序列其中不含stammers, 请构造一个这样的序列并使用最少的关键字.

Example

当 n = 3 只需要使用两个字母 a 和 b 即可: aba and bab. 当 n = 5 时我们需要3个字母，一个例子为： abcab 是一个合法的串。

输入格式

只有一行仅有一个数表示 n , 1 <= n <= 10000000.

输出格式

第一行仅输出一个数，代表使用的关键字种类，然后接下来一行 n 个小写字符表示构造出的合法串.

你可以假设26个小写字母是足够可用的。

样例

样例输入

5  

样例输出

3  

数据范围与提示