Nhà trường dự định lát sàn gỗ cho thư viện mới. Mặt sàn thư viện là một hình chữ nhật có kích thước ~M \times N~ (đơn vị độ dài).

Loại gỗ được chọn là các tấm gỗ hình vuông cao cấp, mỗi tấm có kích thước ~A \times A~ (đơn vị độ dài). Để đảm bảo tính thẩm mỹ, các tấm gỗ được lát song song với các cạnh của căn phòng và phải giữ nguyên vẹn (không được ghép từ các mảnh vụn). Tuy nhiên, ở các mép tường, nếu tấm gỗ bị thừa ra thì thợ sẽ cắt bỏ phần thừa đó đi (nhưng nhà trường vẫn phải mua nguyên cả tấm).

Yêu cầu: Hãy tính số lượng tấm gỗ tối thiểu cần phải mua để lát kín mặt sàn thư viện.

Input

Một dòng duy nhất chứa 3 số nguyên dương ~M, N, A~ (~1 \le M, N, A \le 10^9~).

Output

Ghi ra một số nguyên duy nhất là số lượng tấm gỗ cần mua.

Sample Input 1

6 6 4

Sample Output 1

4

Giải thích:

• Chiều dài 6 cần 2 tấm (vì ~4 + 4 > 6~ nên phải dùng đến tấm thứ 2).
• Tương tự theo chiều rộng 6 cần 2 tấm.
• Tổng số tấm: ~2 \times 2 = 4~ tấm.

Sample Input 2

13 10 3

Sample Output 2

20

Giải thích:

• Theo chiều dài 13 cần 5 tấm (vì ~3 \times 4 = 12 < 13~, nên phải dùng đến tấm thứ 5).
• Theo chiều rộng 10 cần 4 tấm (vì ~3 \times 3 = 9 < 10~, nên phải dùng đến tấm thứ 4).
• Tổng: ~5 \times 4 = 20~ tấm.

Subtasks

• Subtask 1 (50% số điểm): ~M, N, A \le 1000~.
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.

Trong một trò chơi thám tử, Tí nhận được một chuỗi ký tự ~S~ bao gồm các chữ cái in thường và các chữ số. Mật mã để mở két sắt là số nguyên lớn nhất xuất hiện trong chuỗi ký tự đó.

Yêu cầu: Hãy tìm và in ra số nguyên lớn nhất ẩn trong chuỗi ~S~.

Input

Một dòng duy nhất chứa xâu ~S~ (độ dài không quá ~10^5~).

Output

Ghi ra một số nguyên duy nhất là mật mã tìm được. Nếu trong xâu không có số nào, in ra -1.

Sample Input 1

a99b123c888d

Sample Output 1

888

Giải thích: Các số trong xâu là: 99, 123, 888. Số lớn nhất là 888.

Sample Input 2

007and002

Sample Output 2

7

Giải thích: Các số là: 007 (giá trị 7), 002 (giá trị 2). Số lớn nhất là 7.

Sample Input 3

abcde

Sample Output 3

-1

Giải thích: Không có số nào trong xâu.

Subtasks

• Subtask 1 (80% số điểm): Các số trong xâu nhỏ (dưới 18 chữ số).
• Subtask 2 (20% số điểm): Không có ràng buộc gì thêm.

Cho số nguyên dương ~n~, hãy đếm số cặp nghiệm nguyên dương ~(x, y)~ của phương trình thỏa mãn: $$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$$

Ký hiệu ~n! = 1 \times 2 \times 3 \times ... \times n~.

Yêu cầu: Hãy tính số lượng cặp nghiệm nguyên dương ~(x, y)~ thỏa mãn đề bài.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^6~).

Output

Số cặp nghiệm nguyên dương ~(x, y)~ thỏa mãn đề bài chia dư cho ~20252026~.

Sample Input 1

2

Sample Output 1

3

Giải thích: Với ~n = 2~ ta có 3 cặp nghiệm thỏa mãn là: ~(3, 6); (4, 4); (6, 3)~.

Subtasks

• Subtask 1 (50% số điểm): ~n \le 10~.
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.

Cho dãy số nguyên ~a_1, a_2, ..., a_n~ và số nguyên dương ~k~.

Yêu cầu: Thực hiện phép xóa ~k~ phần tử sao cho chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ còn lại là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~n, k~ (~k \le n - 2~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).

Output

Ghi ra một số duy nhất là giá trị lớn nhất tìm được.

Sample Input 1

5 1
4 1 2 3 9

Sample Output 1

1

Giải thích: Xóa 1 phần tử bất kỳ, thì dãy còn lại luôn tồn tại 2 số tự nhiên liên tiếp nhau, nên độ chênh lệch nhỏ nhất là 1.

Sample Input 2

5 2
10 -5 3 -2 1

Sample Output 2

7

Giải thích: Trong các cách xóa 2 phần tử bất kỳ, cách xóa còn 3 phần tử ~\{10, -5, 3\}~ có độ chênh lệch nhỏ nhất là 7. Cách xóa này là cách xóa có độ chênh lệch nhỏ nhất giữa các phần tử là lớn nhất.

Subtasks

• Subtask 1 (20% số điểm): ~n \le 20, k = 1~.
• Subtask 2 (30% số điểm): ~20 < n \le 100~.
• Subtask 3 (25% số điểm): ~100 < n \le 2000~.
• Subtask 4 (25% số điểm): ~2000 < n \le 10^5~.