Kiểm tra thú vị

Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: abcba, abba, xyzzyx... là xâu đối xứng, abc, abab, mnnn không phải là xâu đối xứng.

Bạn được cho một xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái tiếng Anh viết thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Yêu cầu: Hãy tính số lần biến đổi tối thiểu để xâu \(S\) trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu \(S\) thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

• Nhập từ bàn phím xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường.

Output

• In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10\) và chỉ có \(3\) loại ký tự a, b và c, thí sinh sẽ được \(40\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 1000\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^5\), thí sinh sẽ được \(100\) điểm.

Example

abac

abba

abacad

aabbaa

Cho dãy số có quy luật sau: \(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53, 55, 57, 59\ldots\)

Định nghĩa: số ODD là số tự nhiên chỉ chứa các chữ số lẻ \(1, 3, 5, 7, 9\).

Hãy tìm số ODD thứ \(N\) của dãy số.

Input

• Gồm một số duy nhất là số \(N\) \((1 \le N \le 1000000000000)\).

Output

• In ra số ODD thứ \(N\) của dãy số.

Example

6

11

20

59

Nguồn: Thầy Khôi

Số tự nhiên \(x\) được gọi là số siêu lẻ:

• Các chữ số của \(x\) đều là số lẻ
• Tổng các chữ số của \(x\) là số lẻ

Ví dụ: Các số tự nhiên siêu lẻ đầu tiên là: \(1;3;5;7;9;111;113;115;117; ...\)

Yêu cầu: Cho số tự nhiên \(N\). Hãy in ra số siêu lẻ thứ \(N\).

Input

• Gồm 1 dòng duy nhất là số tự nhiên \(N\) (\(1 \le N \le 10^{14}\)).

Output

• In ra số siêu thứ \(N\).

Example

5

9

13

135

55

399

Nguồn: Thầy Khôi

Ông tktungtd là ông chủ của hệ thống đèn giao thông, trong khi đó tknhatbm chỉ làm một nhân viên quèn. Hôm nay tktungtd giao cho tknhatbm một nhiệm vụ đó là lắp các cột đèn giao thông tại Bình Dương. Nhiệm vụ quá là gian đởn, tknhatbm nhận luôn. Trớ trêu thay, do mặt đất của Bình Dương là kim cương, mà kim cương thì rất cứng, tknhatbm phải mất \(69420\) phút để lắp các cột đèn. Sau khi lắp xong các cột đèn, tknhatbm lại bất lực khi Bình Dương có hệ thống đèn giao thông rất độc lạ, không dùng giảm số lùi như các nơi khác mà dùng số nhảy. Cụ thể từ một số nào đó sẽ chuyển thành số bất kì (Ví dụ: Từ số \(10\) chuyển thành số \(60\)). Nhưng tktungtd còn bắt buộc lưu lại chi phí và số lượng thanh của nó nữa. Quá là chán nản, tknhatbm đành đăng lên LQDOJ để nhờ \(69\) anh em bốn phương để giúp mình, còn mình thì đi làm đơn nghỉ việc.

Đèn giao thông này được hiển thị bằng số điện tử, mỗi số đều có một số lượng thanh khác nhau. Ví dụ: Số \(0\) có \(2\) thanh ngang, \(4\) thanh dọc; Số \(1\) có \(2\) thanh dọc; v.v... (xem hình ảnh để hiểu rõ hơn).

Như vậy, để biến đổi từ số \(a\) sang số \(b\) (\(a,b \in \mathbb{N}\)), ta cần thực hiện lần lượt một trong bốn thao tác sau:

• Chọn một thanh bất kì trong số \(a\) và xóa nó đi.
• Thêm một thanh bất kì (ngang hoặc dọc) vào số \(a\).
• Thêm một khuôn rỗng vào bên trái số \(a\).
• Xoá một khuôn rỗng ở bên trái số \(a\).

Điều kiện:

• Các thanh không được xếp chồng lên nhau.
• Mỗi thanh phải được đặt trùng với khuôn của \(1\) chữ số bất kì, không được đặt thanh chéo hoặc đặt không đúng vị trí,....
• Kết quả cuối cùng sau khi biến đổi không được có khuôn rỗng.

Chi phí cho mỗi thao tác thực hiện xoá / thêm là \(1\) Coin.

Yêu cầu: Tính số lượng Coin (chi phí) tối thiểu để biến đổi từ số \(a\) sang số \(b\) để giúp tknhatbm an tâm làm đơn nghỉ việc nhé.

Input

• Một dòng chứa \(2\) số tự nhiên \(a\), \(b\) (\(a,b \leq 10^{96069}\)).

Output

• Dòng đầu tiên in ra hai số \(u\),\(v\) lần lượt là tổng số lượng thanh của \(a\) và \(b\).
• Dòng thứ hai in ra số lượng Coin (chi phí) tối thiểu.

Example

10 60

8 12
6

12 2

7 5
3