Cô Mẫn cùng team đang xây dựng một tính năng mới mang tên "Giải đố nhận tin VIP" cho SetNews. Mỗi ngày, hệ thống sẽ tự động sinh ra một mã khóa bảo mật dựa trên một số nguyên dương \(x\) ban đầu để thử thách người dùng.

Thuật toán tạo mã khóa của SetNews thực hiện chính xác \(k\) bước biến đổi. Ở mỗi bước, giá trị của \(x\) được cập nhật theo quy luật sau:

• Gọi \(a\) là số nguyên tạo thành bằng cách sắp xếp các chữ số của \(x\) theo thứ tự tăng dần (bỏ qua các chữ số \(0\) vô nghĩa ở đầu nếu có).
• Gọi \(b\) là số nguyên tạo thành bằng cách sắp xếp các chữ số của \(x\) theo thứ tự giảm dần.
• Nếu \(x\) là số chẵn, giá trị mới của \(x\) được gán bằng hiệu: \(x = b - a\).
• Nếu \(x\) là số lẻ, giá trị mới của \(x\) được gán bằng hiệu: \(x = x - a\).

Ví dụ, với \(x = 104\):

• \(x\) là số chẵn.
• Sắp xếp tăng dần: \(014 \rightarrow a = 14\).
• Sắp xếp giảm dần: \(410 \rightarrow b = 410\).
• Giá trị \(x\) mới: \(x = 410 - 14 = 396\).

Yêu cầu: Cho giá trị ban đầu \(x\) và số bước biến đổi \(k\), hãy giúp cô Mẫn và team SetNews xác định giá trị cuối cùng của mã khóa \(x\) sau khi thực hiện đủ \(k\) phép biến đổi.

Input

• Dòng duy nhất chứa hai số nguyên dương \(x\) và \(k\) \((1 \le x,k \le 10^{18})\).

Output

• In ra một số nguyên duy nhất là giá trị của \(x\) sau \(k\) bước biến đổi.

Example

21 2

0

104 2

594

Scoring

• Subtask 1 (\(30\%\) số điểm): \(x, k \le 10^5\)
• Subtask 2 (\(30\%\) số điểm): \(x \le 10^{18}, k \le 10^5\)
• Subtask 3 (\(40\%\) số điểm): \(x, k \le 10^{18}\)