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

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