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

Limits: 2 sec., 256 MiB

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

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

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

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

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

Input

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

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

Output

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

Constraints

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

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

Samples