Số đẹp là số được tạo thành từ việc viết liền dãy các số tự nhiên liên tiếp. Ví dụ: \(1011121314\) là một số đẹp tạo thành từ dãy \(10, 11, 12, 13, 14\).

Yêu cầu: Cho trước số đẹp \(S\), tìm số đầu tiên và cuối cùng trong dãy số đã tạo ra \(S\). Nếu tìm thấy nhiều bộ thỏa mãn, ưu tiên chọn theo số đầu nhỏ nhất.

Input

• Dòng duy nhất chứa số đẹp \(S\) (\(1 \le S \le 10^{10^6}\))
• Dữ liệu đảm bảo số đẹp \(S\) được tạo từ dãy số tự nhiên có giá trị không quá \(10^6\)

Output

• Một dòng duy nhất chứa số đầu tiên và số cuối cùng của dãy, cách nhau bởi dấu cách

Example

9101112

9 12

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(S \le 10^9\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc thêm