Cho một bảng hình chữ nhật kích thước ~m \times n~ được chia thành lưới ô vuông đơn vị ~m~ hàng, ~n~ cột. Các hàng đánh số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới và các cột đánh số từ ~1~ đến ~n~ theo thứ tự từ trái qua phải.

Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột ~j~ sẽ được tô màu từ trên xuống dưới: ~h_j~ ô màu vàng tiếp đến là ~m - h_j~ ô màu xanh. Như vậy tình trạng màu trên bảng hoàn toàn xác định nếu như ta biết được số hàng ~m~, số cột ~n~ và các số nguyên ~h_1,h_2, \dots, h_n~.

Hãy xác định một hình chữ nhật ~R~ gồm các ô trong bảng thỏa mãn điều kiện sau:

• ~R~ có cạnh song song với các cạnh bảng và mỗi ô của bảng thì hoặc nằm trong ~R~ hoặc nằm ngoài ~R~.
• ~R~ là đơn sắc (chỉ gồm các ô màu vàng hoặc chỉ gồm các ô màu xanh).
• Diện tích của ~R~ là lớn nhất có thể.

Input

• Dòng đầu chứa hai số nguyên dương ~m, n\ (1\le m,n\le 10^6)~;
• Dòng tiếp theo chứa ~n~ số nguyên ~h_1, h_2, \dots, h_n\ (0\le h_i\le m)~.

Output

• Dòng đầu tiên ghi diện tích hình chữ nhật tìm được.
• Dòng thứ hai ghi chỉ số hàng và chỉ số cột của ô góc trên bên trái của hình chữ nhật tìm được.
• Dòng thứ ba ghi chỉ số hàng và chỉ số cột của ô góc dưới bên phải của hình chữ nhật tìm được.

Example

Input

5 9
1 3 4 4 5 4 4 3 1

Output

21
1 2
3 8