Паліндромно менший рядок

Обмеження: 2 сек., 256 МіБ

У Зеника є рядок \(s\), який складається з \(n\) малих латинських букв. Марічці цікаво знайти такий рядок \(t\), що також складається з \(n\) малих латинських букв, і виконуються наступні умови:

• Для кожної пари \(i, j\) \((i \le j)\), якщо підрядок \(s[i..j]\) не є паліндромом, то і підрядок \(t[i..j]\) також не є паліндромом.

• Кількість різних букв в рядку \(t\) є мінімально можливою.

Допоможіть Марічці знайти такий рядок \(t\).

Паліндромом називається рядок, який читається однаково зліва направо та справа наліво.

Вхідні дані

У першому рядку задано єдине ціле число \(n\) — довжина рядка \(s\).

У другому рядку задано \(s\) — рядок довжини \(n\).

Вихідні дані

У єдиному рядку виведіть шуканий рядок \(t\). Якщо таких рядків існує декілька, виведіть будь-який з них.

Обмеження

\(1 \le n \le 2 \cdot 10^5\),

Рядок \(s\) складається з маленьких латинських букв.

Приклади