Trong một phòng thí nghiệm vật lý, nhóm nghiên cứu của Tiến sĩ An đang phân tích dữ liệu năng lượng thu được từ ~n~ thí nghiệm độc lập. Mỗi thí nghiệm cho ra một giá trị năng lượng nguyên dương ~a_1, a_2, \ldots, a_n~. Để đánh giá mức tương tác cực đại giữa hai cặp thí nghiệm, nhóm nghiên cứu định nghĩa chỉ số chênh lệch năng lượng như sau:

Chọn bốn chỉ số khác nhau ~i, j, k, l~ (~1 \le i, j, k, l \le n~; ~i, j, k, l~ đôi một khác nhau) sao cho giá trị ~(a_i-a_j)\times(a_k-a_l)~ là lớn nhất.

Giá trị lớn nhất này được dùng để đánh giá độ biến thiên năng lượng cực đại của hệ thí nghiệm. Do khối lượng dữ liệu rất lớn, Tiến sĩ An nhờ bạn viết chương trình tính toán chỉ số này.

Input

• Dòng thứ nhất chứa số nguyên ~n~ (~4 \le n \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).

Output

Ghi ra một số nguyên là chỉ số chênh lệch năng lượng lớn nhất có thể đạt được.

Ví dụ 1

Input

5
1 3 5 7 9

Output

36

Giải thích

Chọn ~i=5, j=2, k=4, l=1~ sẽ được ~(a_i-a_j)\times(a_k-a_l)=(9-3)\times(7-1)=36~, lớn nhất.

Ví dụ 2

Input

10
2 8 7 4 10 5 1 3 3 6

Output

56

Giải thích

Chọn ~i=2, j=7, k=5, l=1~ sẽ được ~(a_i-a_j)\times(a_k-a_l)=(8-1)\times(10-2)=56~, lớn nhất.

Ràng buộc

• Có ~30\%~ số test thỏa ~4 \le n \le 50~.
• ~70\%~ số test không có thêm ràng buộc nào.

Trong một nghiên cứu sinh học, mỗi gen đặc biệt được gán một mã số là số nguyên tố.

Khi ghép hai gen khác nhau, mức độ tác động sinh học của cặp gen đó được tính bằng tích hai mã số gen. Do giới hạn an toàn của thí nghiệm, mức độ tác động sinh học không được vượt quá ~n~.

Yêu cầu: Cho số nguyên dương ~n~. Hãy tìm hai gen có mã số là hai số nguyên tố khác nhau sao cho tích của hai mã số là lớn nhất và tích đó không vượt quá ~n~.

Input

Chứa số nguyên dương ~n~ (~6 \le n \le 10^9~).

Output

Ghi hai số nguyên tố tìm được cách nhau một khoảng trắng, số nhỏ đứng trước, số lớn đứng sau.

Giới hạn

• ~50\%~ số test thỏa ~n \le 10^4~.
• ~50\%~ số test không có ràng buộc gì thêm.

Ví dụ

Input

28

Output

2 13

Giải thích

Với giá trị số nguyên dương ~n=28~ thì ta sẽ tìm được hai số nguyên tố ~2~ và ~13~ có tích là ~26~ (~2\times13~) lớn nhất và giá trị ~26~ này không vượt quá giá trị ~28~.

Một bệnh viện cần được trực cấp cứu liên tục trong ~n~ giờ để đảm bảo luôn sẵn sàng tiếp nhận bệnh nhân. Thời điểm bắt đầu được tính từ ~0~. Bệnh viện có danh sách ~m~ bác sĩ có thể phân công trực. Các bác sĩ được đánh số từ ~1~ đến ~m~. Bác sĩ thứ ~i~ trực từ thời điểm ~s_i~ đến thời điểm ~t_i~ (~0 \le s_i < t_i \le n~) với chi phí trực là ~c_i~.

Yêu cầu: Hãy chọn một số bác sĩ sao cho: tại mọi thời điểm trong khoảng từ ~0~ đến ~n~, luôn có ít nhất một bác sĩ trực và tổng chi phí trực là nhỏ nhất. Dữ liệu đảm bảo luôn tồn tại phương án hợp lệ.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ (~0 < n,m \le 100~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm ~s_i, t_i, c_i~ (~0 \le s_i < t_i \le n;\ 0 < c_i \le 10^9~).

Output

Một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả).

Ví dụ

Input

9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

Output

66

Giải thích

Chọn các bác sĩ trực trong các khung giờ:

• ~0-5~ (chi phí ~25~)
• ~3-7~ (chi phí ~21~)
• ~7-9~ (chi phí ~20~)

Tổng chi phí trực là ~66~ và bệnh viện luôn có bác sĩ trực cấp cứu.

Trong một hệ thống bảo mật thông tin, các tham số khóa trung gian được biểu diễn dưới dạng phân số. Giữa mỗi cặp tham số liên tiếp, kỹ sư bảo mật được phép chèn một trong ba phép toán:

• +: kết hợp khóa
• -: loại bỏ thành phần khóa
• X: tăng cường mã hóa.

Khóa mã hóa cuối cùng chính là giá trị của biểu thức mà kỹ sư bảo mật đã tạo.

Yêu cầu: Hãy giúp kỹ sự tạo ra khóa mã hóa cuối cùng có giá trị chính xác bằng ~R~.

Input

• Dòng đầu ghi số ~N~ (~N \le 12~).
• Dòng thứ hai ghi ~N~ phân số, các phân số cách nhau một dấu cách. Tử số và mẫu số của mỗi phân số phân cách nhau bởi dấu chia /.
• Dòng cuối cùng ghi phân số ~R~.

Tử số và mẫu số của các số hạng có trị tuyệt đối không quá ~20~. Tử số và mẫu số của số ~R~ có trị tuyệt đối không quá ~10^5~.

Output

Ghi một xâu gồm các kí tự dấu phép tính của biểu thức lần lượt từ trái qua phải. Nếu có nhiều đáp án, thì xuất xâu đáp án có thứ tự từ điển nhỏ nhất. Lưu ý: phép nhân là kí tự X hoa.

Ví dụ

Input

4
5/2 4/6 3/8 -2/3
19/12

Output

-+X

Giải thích

~\frac{5}{2}-\frac{4}{6}+\frac{3}{8}\times\left(-\frac{2}{3}\right)=\frac{19}{12}~.