Số palindromic hàng xóm

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho một số palindromic \(N\). Nhiệm vụ là tìm số palindromic nhỏ nhất lớn hơn \(N\) bằng cách sử dụng cùng một bộ chữ số như trong \(N\).

Input

Dòng đầu tiên nhập vào số nguyên \(N\). Số lượng chữ số của \(N\) không quá \(10^5\).

Output

In ra kết quả cùa bài toán. Nếu không có đáp án vui lòng in ra \(-1\).

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

35453

Output

53435

Ví dụ 2

Input

33

Output

-1

Giải thích ví dụ

Ví dụ

Ví dụ 3

Input

35453

Output

53435

**Giải thích:** Số palindromic nhỏ nhất lớn hơn 35453 với cùng bộ chữ số là 53435.

Ví dụ 4

Input

33

Output

-1

**Giải thích:** Không thể tạo ra số palindromic lớn hơn 33 từ các chữ số của nó.

Thông tin học tập

• Buổi: B21
• Concepts: std::string, palindromes, next permutation, half-string sorting
• Giới hạn kiến thức: B01-B21
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30