Một số nguyên dương được gọi là số tròn nếu tất cả các chữ số của nó ngoại trừ chữ số ngoài cùng bên trái đều bằng không (bao gồm các số từ 1 đến 9).

Ví dụ các số tròn: 1000, 2, 9, 300, 70. Các số không tròn: 110, 505, 222, 10001.

Bạn được cho một số nguyên dương N (1 ≤ N ≤ 10¹⁸). Hãy biểu diễn số N thành tổng các số tròn sao cho số lượng số hạng là ít nhất

Input

• Một số nguyên dương N (1 ≤ N ≤ 10¹⁸)

Output

• Các số hạng là tròn số được sắp xếp theo thứ tự tăng dần

Sample

Cho số nguyên X gồm N chữ số dạng a₁a₂a_N Trọng số của N được tính theo công thức: 1 x a₁ + 2 x a₂ + … + N x a_N

Ví dụ: N = 2023 có trọng số là 2 x 1 + 0 x 2 + 2 x 3 + 3 x 4 = 20

Các chữ số của N có 1 chữ số tại 1 vị trí nào đó bị thay bằng dấu "?".

Yêu cầu

Tìm giá trị nhỏ nhất của chữ số bị thay thế này để trọng số của N chia hết cho 7. Ví dụ: N = 2?13, "?" có thể là chữ số 2, khi đó N = 2213 có trọng số 21 + 22 + 13 + 34 = 21, chia hết cho 7.

Dữ liệu vào

Nhập từ bàn phím số nguyên dương N, trong đó có 1 chữ số thay bằng dấu? (N<10¹⁰⁰)

Dữ liệu ra

Ghi ra màn hình chữ số nhỏ nhất có thể thay vào dấu "?", nếu không tồn tại chữ số nào thì ghi -1.

Giới hạn:

• 50% test có N<10⁹
• 50% test có N≤10¹⁰⁰.

Ví dụ

Bạn được cho hai số nguyên dương N và K. Hãy tìm số nguyên thứ K mà không chia hết cho N

Ví dụ: N = 3 và K = 7. Tất cả các số không chia hết cho 3: 1, 2, 4, 5, 7, 8, 10, 11, 13... Số thứ 7 là 10

Dữ liệu vào

• Hai số nguyên dương N (1 ≤ N ≤ 10⁹) và K (1 ≤ K ≤ 10⁹).

Dữ liệu ra

• In ra số nguyên thứ K không chia hết cho N

Ví dụ

Thảo là một người vui vẻ, vì vậy mỗi khi buồn chán, anh ấy sẽ nghĩ ra các trò chơi mới. Vào đêm đông gió lạnh, anh ấy nghĩ ra một trò chơi và quyết định chơi nó.

Có N lá bài nằm ngang được sắp xếp từ trái sang phải, mỗi lá bài sẽ mang giá trị nguyên dương bất kỳ. Người chơi có thể thực hiện nhiều bước. Trong mỗi bước, người chơi có thể chọn một lá bài trong dãy mang giá trị là X và loại bỏ nó, khi đó tất cả các lá bài có giá trị là X - 1 và X + 1 đều sẽ bị loại bỏ. Bước đó sẽ mạng lại X điểm cho người chơi.

Thảo sẽ rất vui nếu được càng nhiều điểm càng tốt. Hãy giúp anh ấy.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên duy nhất N (1≤ N ≤ 100.000).
• Dòng thứ hai gồm N số a1, a2, ..., aN, mỗi số cách nhau một khoảng trắng (0 ≤ ai ≤ 100.000) tương ứng với giá trị mỗi lá bài từ trái sang phải.

Dữ liệu ra

• Một số nguyên dương là số điểm lớn nhất mà Thảo có thể đạt được.

Ví dụ

Giải thích:

Trường hợp 2, Thảo sẽ chọn lá bài mang giá trị là 2 ở vị trí bất kỳ, khi loại bỏ sẽ còn những lá mang giá trị [2, 2, 2, 2]. Sau đó thực hiện 4 bước, mỗi bước chọn bất kỳ phần tử nào bằng 2. Tổng cộng có thể kiếm được 10 điểm