Nhập vào dãy số gồm \(N\) số tự nhiên \((10 \le N \le 40)\). Xuất ra số có số lần xuất hiện nhiều nhất và số lần xuất hiện tương ứng.

Lưu ý: Trong trường hợp có nhiều kết quả đúng theo yêu cầu thì lấy kết quả của số có giá trị lớn nhất.

Input

• Dòng 1 ghi giá trị số \(N\).
• Dòng 2 ghi dãy số gồm \(N\) số tự nhiên (mỗi giá trị cách nhau ít nhất một khoảng trắng).

Output

• Gồm một dòng ghi số có số lần xuất hiện nhiều nhất và số lần xuất hiện tương ứng (mỗi giá trị cách nhau ít nhất một khoảng trắng).

Example

12
9 52 11 11 52 11 9 6 11 52 52 6

52 4

Trộn hai xâu ký tự và sắp xếp theo chiều giảm dần của các chữ cái tiếng Anh (phân biệt chữ hoa và chữ thường) sau khi đã loại bỏ các ký tự không phải là chữ cái.

Input

• Dòng đầu tiên ghi xâu ký tự thứ nhất.
• Dòng thứ hai ghi xâu ký tự thứ hai.
• Các xâu kí tự chỉ gồm các chữ cái và các chữ số, mỗi xâu có độ dài không quá \(2000\).

Output

• Ghi ra kết quả tìm được theo yêu cầu đề bài.

Lưu ý: Xâu ký tự là chữ hoa được sắp xếp đứng trước xâu ký tự chữ thường.

Example

1a2c3b4d5f6e7XZY
yzx8FEDCBA9

ZYXFEDCBAzyxfedcba

Một điểm rút tiền ATM có các loại tiền mệnh giá lần lượt như sau: \(10.000\) đồng, \(20.000\) đồng, \(50.000\) đồng, \(100.000\) đồng, \(200.000\) đồng và \(500.000\) đồng (mỗi loại không quá \(1.000\) tờ). Một khách hàng cần rút ra một số tiền \(M\) đồng (giả sử rằng sau khi đã kiểm tra đầy đủ các thông số về bảo mật cá nhân). Biết rằng số tiền giới hạn mỗi lần rút tại điểm rút tiền ATM có giá trị thấp nhất là \(50.000\) đồng. Hãy tìm cách trả sao cho khách hàng nhận được số lượng tờ tiền là ít nhất.

Input

• Nhập vào một số là số tiền cần rút (theo quy định số tiền cần rút có đơn vị tính được làm tròn theo mệnh giá tiền có giá trị thấp nhất là 10.000 đồng).

Output

• Nếu không có cách trả thì ghi 1 dòng duy nhất có nội dung: KHONG THUC HIEN DUOC.
• Nếu có cách trả thì:
  • Dòng 1: ghi số lượng tờ tiền ít nhất phải trả.
  • Dòng 2: ghi các số tương ứng với số tiền cần trả cho mỗi loại tiền theo thứ tự: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng.

Example

9870000

23
0 1 1 1 1 19