Một lớp học gồm \(N\) bạn tổ chức đi dã ngoại. Để thuận tiện cho việc quản lí và tổ chức các hoạt động vui chơi, \(N\) bạn được chia thành không quá \(26\) nhóm.

Vì có không quá \(26\) nhóm nên mỗi nhóm được đặt tên theo một kí tự latin thường, tức là sử dụng các kí tự trong tập {'a', 'b', ..., 'z'}.

\(N\) bạn đang xếp thành một hàng dọc để chuẩn bị điểm danh và lên xe, bạn thứ \(i\) (\(1 \leq i \leq N\)) thuộc nhóm \(S_i\) (\(S_i\) là một kí tự latin thường). Tưởng rằng chuẩn bị được lên xe và đi chơi liền, nhưng một sự cố đã xảy ra khiến chuyến đi bị delay khoảng 1 tiếng. Trong thời gian này, các bạn quyết định giao lưu làm quen với nhau, nhưng vẫn muốn giữ hàng để có thể lên xe bất cứ lúc nào.

Trước khi đi chơi, các bạn cùng nhóm đã được gặp nhau rất nhiều để thảo luận trước kế hoạch đi chơi sắp tới, vì vậy các bạn muốn tìm một thứ tự xếp hàng khác để được tiếp xúc với các bạn khác nhóm trong thời gian chờ.

Yêu cầu: Tìm một hoán vị có thứ tự từ điển nhỏ nhất của xâu S, sao cho không có hai kí tự liền kề nhau và bằng nhau.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) là số bạn đi dã ngoại.
• Dòng thứ hai chứa một xâu S gồm \(N\) kí tự, mỗi kí tự là một chữ cái latin thường.

Output

• Một xâu là hoán vị của xâu S thỏa mãn yêu cầu đề bài, hoặc đưa ra -1 nếu không tồn tại xâu thỏa mãn yêu cầu.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): $S_i \in { \text{a, b, c} }$.
• Subtask \(3\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

6
cavaer

acaerv

9
didadiddu

dadididud

3
aaa

-1