Một công ty lớn đã quyết định đưa ra một loại màn hình có đúng \(n\) điểm ảnh được xếp thành các hàng và các cột.

Nhiệm vụ của bạn là xác định số hàng điểm ảnh \(a\) và số cột điểm ảnh \(b\) sao cho:

• Có đúng \(n\) điểm ảnh trên màn hình, tức là \(a \times b = n\);
• Số hàng điểm ảnh không vượt quá số cột điểm ảnh, tức là \(a \leq b\);
• Sự khác biệt \(b - a\) càng nhỏ càng tốt;

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) (\(1 \leq n \leq 10^{9}\)).

Output

• Gồm một dòng chứa hai số nguyên tương ứng là số hàng và số cột điểm ảnh cần tìm của màn hình.

Scoring

• Có 30% số điểm tương ứng với: \(1 \leq n \leq 10^{3}\);
• Có 30% số điểm tương ứng với: \(1 \leq n \leq 10^{7}\);
• Có 40% số điểm : Không có thêm ràng buộc nào.

Example

8

2 4

25

5 5

Dãy số \(a_1, a_2, \ldots, a_n\) được gọi là tăng nếu \(a_1 < a_2 < \cdots < a_n\).

Bạn được cho một dãy số \(b_1, b_2, \ldots, b_n\) và một số nguyên dương \(d\). Trong mỗi lần thao tác, bạn chọn một phần tử của dãy số và cộng thêm \(d\) vào nó. Số thao tác ít nhất là bao nhiêu để biến đổi dãy số đã cho trở thành dãy số tăng.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(d\) (\(1 \leq n \leq 10^5\); \(1 \leq d \leq 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên tương ứng là dãy số \(b_1, b_2, ..., b_n\) (\(1 \leq b_i \leq 10^9\)).

Output

• Gồm một số nguyên là số thao tác ít nhất để biến đổi dãy số đã cho trở thành dãy số tăng.

Scoring

• Có 30% số test ứng với 30% số điểm thỏa mãn: \(1 \leq n, d, b_i \leq 10^2\).
• 30% số test khác ứng với 30% số điểm thỏa mãn: \(1 \leq n \leq 10^3\) và \(1 \leq d, b_i \leq 10^6\).
• 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Example

4 2
1 3 3 2

3

Mẹ của An đã lên kế hoạch ăn sáng bằng bánh mì hoặc bánh rán cho An trong \(n\) ngày (được đánh số từ \(1\) đến \(n\)). Mẹ của An đã viết một mảng \(s\) độ dài \(n\), trong đó phần tử thứ \(i\) (\(1 \leq i \leq n\)) là '0' hoặc '1' biểu thị ngày thứ \(i\) sẽ ăn bánh mì hoặc bánh rán tương ứng.

An thích ăn bánh rán hơn bánh mì, nên anh ta muốn chọn một đoạn gồm \(k\) kí tự liên tiếp trong mảng \(s\) và thay đổi mỗi kí tự '0' trong đoạn này thành '1'. Gọi \(time\) là số ngày liên tiếp dài nhất mà An ăn bánh rán. Bạn hãy giúp An tìm giá trị \(time\) lớn nhất mà anh ta có thể đạt được bằng cách chọn một đoạn hợp lý.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq k \leq n \leq 10^6\)).
• Dòng thứ hai chứa mảng \(s\) độ dài \(n\), chỉ gồm các kí tự '0', '1'.

Output

• Gồm một số nguyên là số \(time\) lớn nhất.

Scoring

• Có 30% số test ứng với 30% số điểm thỏa mãn: \(1 \leq k \leq n \leq 10^2\).
• 30% số test khác ứng với 30% số điểm thỏa mãn: \(1 \leq k \leq n \leq 10^3\).
• 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Example

13 2
0 1 0 1 1 1 0 0 0 0 1 0 1

5

6 3 
1 0 0 0 0 1

4

Trước giờ học giáo dục thể chất, một lớp gồm \(n\) học sinh xếp thành một hàng. Tất cả học sinh trong lớp đều có chiều cao khác nhau. Vị trí thứ \(i\) (i = 1, 2, ..., n) tính từ đầu bên trái của hàng là học sinh có chiều cao \(pi\) (\(1 ≤ p_i ≤ n\)).

Khi bắt đầu giờ học, thầy giáo có thể thay đổi thứ tự học sinh trong hàng. Để làm điều này, thầy giáo có thể thực hiện thao tác sau đúng một lần: chọn một đoạn từ vị trí \(l\) đến vị trí \(r\) (\(1 ≤ l ≤ r ≤ n\)) và sắp xếp các học sinh trong đoạn này theo chiều cao tăng dần từ trái sang phải. Ví dụ \(n = 5\), ban đầu học sinh theo thứ tự có chiều cao là 5, 2, 4, 1, 3 và thầy giáo chọn \(l = 1, r = 4\) thì sau khi sắp xếp học sinh sẽ theo thứ tự có chiều cao là 1, 2, 4, 5, 3.

Sử dụng thao tác này, thầy giáo có thể sắp xếp để hai học sinh nào đó cách xa nhau nhất có thể. Khoảng cách giữa hai học sinh bằng sự chênh lệch giữa các vị trí mà hai học sinh đứng. Với mỗi cặp học sinh, thầy giáo tính khoảng cách lớn nhất giữa hai học sinh này sau khi thực hiện đúng 1 thao tác nói trên. Bạn hãy giúp thầy giáo tìm tổng của các giá trị này.

Cụ thể hơn, hãy xét hai học sinh ban đầu ở vị trí \(i\) và \(j\) (\(1 ≤ i < j ≤ n\)). Gọi \(d(i, j)\) là khoảng cách lớn nhất giữa hai học sinh đó mà thầy giáo có thể đạt được bằng cách chọn một đoạn và sắp xếp. Bạn cần tính tổng tất cả các giá trị \(d(i, j)\) với mọi \(i, j\) thỏa mãn \(1 ≤ i < j ≤ n\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) là số học sinh trong lớp (\(2 ≤ n ≤ 3000\)).
• Dòng thứ hai chứa n số nguyên \(p_1, p_2, ..., p_n\) là chiều cao của từng học sinh trong hàng (\(1 ≤ p_i ≤ n\)). Dữ liệu đảm bảo rằng tất cả các số \(p_i\) đều phân biệt.

Output

• Gồm một số nguyên là câu trả lời cho bài toán.

Scoring

• Có 20% số test ứng với 30% số điểm thỏa mãn: \(n \leq 10\).
• Có 20% số test ứng với 30% số điểm thỏa mãn: \(n \leq 50\).
• Có 20% số test ứng với 30% số điểm thỏa mãn: \(n \leq 100\).
• Có 20% số test ứng với 30% số điểm thỏa mãn: \(n \leq 600\).
• 20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.

Example

5
5 2 4 1 3

35

10
2 1 6 8 3 5 9 10 7 4

256

2
2 1

1