Dino đang học về thời gian. Bố đố Dino: giả sử hiện tại là 00:00:00, hỏi sau ~N~ giây thì là thời gian nào? Bạn hãy cùng Dino giải quyết bài toán này.

Dữ liệu vào từ tệp văn bản: NGIAY.INP

• Gồm một dòng chứa một số nguyên ~N~ ~(0 \le N < 86400)~.

Kết quả ghi ra tệp văn bản: NGIAY.OUT

In ra trên một dòng chuỗi thời gian dưới định dạng HH:MM:SS, trong đó:

• HH: giờ ~(0 \le HH ≤ 23)~.
• MM: phút ~(0 \le MM \le 59)~.
• SS: giây ~(0 \le SS \le 59)~.

Sample Input 1

59

Sample Output 1

00:00:59

Sample Input 2

3661

Sample Output 2

01:01:01

Cho một số nguyên ~x~. Viết chương trình tính:

~f(x) = x^{10} + x^5 + 1~

Input

Gồm một số nguyên ~x~ duy nhất. (~|x| \leq 50~)

Output

In ra giá trị biểu thức ~f(x)~.

Sample Test

Input:

2

Output:

1057

Cho hai số nguyên dương ~a~, ~n~. Tính ~a^n~.

Input

Gồm một dòng chứa hai số nguyên dương ~a~, ~n~. (~a, n \leq 20~)

Dữ liệu đảm bảo ~a^n~ luôn nhỏ hơn ~10^{19}~.

Output

In ra giá trị ~a^n~.

Sample Test

Input:

2 3

Output:

8

Người ta muốn xây dựng một tuyến đường qua một vùng đất. Tuyến đường được chia thành ~N~ đoạn. Để làm được việc này người ta phải san nền cho vùng đất mà tuyến đường sẽ di qua. Ban đầu, nền đường tại đoạn thứ ~i~ (~1 \leq i \leq N~) có độ cao là ~h_i~ và người ta muốn sau khi san nền, tại tất cả các đoạn đường, nền đường đều có cùng một độ cao là ~k~.

Yêu cầu: Cho biết độ cao ~k~ của nền đường, hãy tính tổng chi phí cần bỏ ra để san nền cho ~N~ đoạn đường với độ cao ~k~.

Input

• Dòng đầu tiên ghi 2 số nguyên dương ~N, M~ lần lượt là số đoạn đường cần san nền và số bộ dữ liệu, mỗi bộ tương ứng với một số nguyên dương ~k~ (~1 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq k \leq 10^9~),
• Dòng thứ hai chứa ~N~ số nguyên dương ~h_1, h_2, ..., h_N~ với ~h_i~ là độ cao của nền đường tại đoạn thứ ~i~ (~1 \leq h_i \leq 10^9, 1 \leq i \leq N~);
• ~M~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• Gồm ~M~ dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả tính được theo dữ liệu vào.

Subtask

• Có ~60~% số test ứng với ~60~% số điểm thỏa mãn: ~1 \leq N \leq 10^3, 1 \leq M \leq 10^3~;
• ~40~% số test còn lại ứng với ~40~% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 3
3 2 7 1 9
4
1
6

Output

14
17
16