Palindrome-smaller string

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a string \(s\) consisting of \(n\) lowercase Latin letters. Marichka is interested in finding a string \(t\), also consisting of \(n\) lowercase Latin letters, such that the following conditions are met:

• For every pair \(i, j\) \((i \le j)\), if the substring \(s[i..j]\) is not a palindrome, then the substring \(t[i..j]\) is also not a palindrome.

• The number of distinct letters in the string \(t\) is the minimum possible.

Help Marichka find such a string \(t\).

A palindrome is a string that reads the same forwards and backwards.

Input

The first line contains a single integer \(n\) — the length of the string \(s\).

The second line contains \(s\) — a string of length \(n\).

Output

In a single line, output the desired string \(t\). If there are multiple such strings, output any of them.

Constraints

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

The string \(s\) consists of lowercase Latin letters.

Samples