Merkkijono (String)

• Time limit: 1.00 s
• Memory limit: 512 MB

Merkkijonossa on alussa vain merkki a. Tämän jälkeen joka askeleella merkkijonon alkuun, loppuun ja kaikkiin väleihin lisätään seuraava merkki aakkosissa. Merkkijono alkaa muodostua seuraavasti:

1. a
   
2. bab
   
3. cbcacbc
   
4. dcdbdcdadcdbdcd
   
5. ...
   

Mikä on merkkijonon sisältö vaiheessa $n$?

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Tulosta merkkijonon sisältö vaiheessa $n$.

Esimerkki

Syöte:
3

Tuloste:
cbcacbc

Arvostelu

Kaikissa testeissä $1 \le n \le 16$. Saat tehtävästä $100$ pistettä, jos koodisi tuottaa oikean vastauksen jokaisessa testissä.

---

A string initially contains only the character a. At each subsequent step, the next character from the alphabet is added to the beginning and end of the string, and between each existing character. The string starts forming as follows:

1. a
   
2. bab
   
3. cbcacbc
   
4. dcdbdcdadcdbdcd
   
5. ...
   

What are the contents of the string at step $n$?

Input

The only line of input contains the integer $n$.

Output

Print the contents of the string at step $n$.

Example

Input:
3

Output:
cbcacbc

Grading

For each test, $1 \le n \le 16$. You will get $100$ points from the task if your code produces the correct answer to each test.