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 xâu ~X~ có độ dài xâu không quá ~10^4~, chỉ gồm các kí tự tiếng Anh in hoa. Viết liên tiếp ~K~ lần xâu ~X~ được xâu ~S~. Hỏi có bao nhiêu xâu HN được tạo ra bằng cách xoá các kí tự từ xâu ~S~.

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

• Dòng đầu tiên chứa xâu ~X~;
• Dòng thứ hai chứa một số nguyên dương ~K~ (~K \leq 10^9~).

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

• In ra kết quả của bài toán sau khi chia lấy dư cho ~10^9 + 7~.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~K = 1~;
• Subtask 2 (~20\%~ số điểm): ~K \leq 10^3~;
• Subtask 3 (~20\%~ số điểm): ~K \leq 10^6~;
• Subtask 4 (~10\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

HNNH
2

Sample Output

8

Giải thích

• Xâu ~S~ có dạng HNNHHNNH.
• Các bộ vị trí tạo thành xâu HN thỏa mãn là ~(1, 2), (1, 3), (1, 6), (1, 7), (4, 6), (4, 7), (5, 6), (5, 7)~.

Hùng đang trải nghiệm tựa game mới mua đầu năm, trong màn chơi hiện tại thì Hùng đang gặp một trở ngại khá lớn. Màn chơi có ~N~ tòa tháp, tòa tháp thứ ~i~ có độ cao là ~H_i~. Hiện tại ở tòa tháp thứ ~1~, Hùng đang có một chiếc máy bay với độ an toàn bay là ~K~. Trong một lần bay, Hùng có thể điều khiển máy bay từ tòa tháp ~i~ bay đến một tòa tháp ~j~ ~(i < j)~, với điều kiện ~|H_i - H_j| \le K~ vì nếu không máy bay có thể đâm vào tháp và cậu sẽ thua.

Cho dữ liệu của màn chơi, bạn hãy kiểm tra xem với mỗi tòa tháp thì có tồn tại cách để Hùng bay đến hay không?

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

• Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(1 \le N \le 2 \cdot 10^5)~ và ~K~ ~(1 \le K \le 10^9)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~H_1, H_2, \ldots H_N~, với ~H_i~ là độ cao của tòa tháp thứ ~i~ ~(1 \le H_i \le 10^9)~.

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

• In ra trên một dòng ~N~ số nguyên ~0~ hoặc ~1~, số thứ ~i~ là ~1~ nếu Hùng có thể bay đến tòa tháp đó, và ~0~ nếu ngược lại.

Subtasks

• Subtask 1 (~40\%~ số điểm): ~H_1 < H_2 < \ldots < H_N~.
• Subtask 2 (~30\%~ số điểm): ~N \le 1000~.
• Subtask 3 (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

5 2
5 4 8 7 2

Sample Output

1 1 0 1 1

Giải thích: Hùng có thể đi đến các tòa tháp ~1, 2, 4, 5~ như sau:

• Tháp ~1~: Hùng ban đầu đã ở tháp ~1~.
• Tháp ~2~: Đi từ ~1~ đến ~2~.
• Tháp ~4~: Đi từ ~1~ đến ~4~.
• Tháp ~5~: Đi từ ~1~ đến ~2~ rồi đến ~5~.

Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của ~4~ số tự nhiên liên tiếp hay không, nếu có hãy đưa ra số nhỏ nhất trong ~4~ số đó.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~N \le 10^9~)

Output

In ra số nhỏ nhất trong ~4~ số nếu ~N~ là tổng của ~4~ số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

10

Output:

1

Note: Do ~10 = 1 + 2 + 3 + 4~ nên ~10~ là tổng của bốn số tự nhiên liên tiếp.

Sample Test 2

Input:

12

Output:

NO