Đồng hồ bấm giờ tại một cuộc thi điền kinh chỉ đo và hiển thị thời gian ở đơn vị giây nhưng bảng điện tử lại chỉ hỗ trợ định dạng hh:mm:ss. Do đó, ban tổ chức muốn có một chương trình có thể chuyển đổi giá trị này sang định dạng hh:mm:ss để có thể hiển thị lên bảng điện tử.

Bạn hãy giúp ban tổ chức viết chương trình thực hiện công việc chuyển đổi này nhé.

Input

Vào từ thiết bị nhập chuẩn gồm 1 dòng ghi số ~m, (0 \le m \le 10^{18})~

Output

Ghi ra thiết bị xuất chuẩn gồm 1 dòng ghi thời gian ở dạng hh:mm:ss.

Sample

Input #1

1234

Output #1

00:20:34

Hiện nay trên internet có hàng tá game như thế này.

Game trong hình có tên là Clone run. Bạn cần đi qua các cửa, mỗi cửa sẽ có 2 lựa chọn với các phép toán cộng, trừ, nhân hay chia số clone của bạn với một số lượng tùy thuộc vào phép tính và con số trên cánh cửa. Mục tiêu của trò chơi là bạn cần đi sao cho số lượng clone của bạn là lớn nhất có thể.

Vì quá chán nên bạn quyết định làm một con bot tự động chơi thay cho bạn.

Lưu ý:

• Số lượng clone không thể là số âm. Vậy nên nếu số lượng clone bị giảm xuống số âm, ta xem như bằng 0.
• Số lượng clone không thể là số thập phân nên khi chia ta chỉ lấy phần nguyên. VD: ~5/2 = 2~

Input

Định dạng đầu vào như sau:

X N
a1 b1 c1 d1
a2 b2 c2 d2
...
aN bN cN bN

• Dòng đầu tiên gồm hai số ~X~ là số clone bạn bắt đầu, ~N~ là số lượng cửa bạn cần đi qua.
• ~N~ dòng tiếp theo, mỗi dòng chứa thông tin của hai cửa bạn cần đi qua là ~a_i, b_i, c_i, d_i~
  • ~a_i, c_i~ là phép tính +, -, *, / (~a_i~ là cửa trái, ~c_i~ là cửa phải)
  • ~b_i, d_i~ là số nguyên (~b_i~ là cửa trái, ~d_i~ là cửa phải)

Output

• Một dòng duy nhất chứa một số là số lượng clone nhiều nhất bạn có thể lấy được.

Giới hạn

• ~1 \le N \le 1000~
• ~0 \le X \le 1000~
• ~-1000 \le a_i, c_i \le 1000~
• ~a_i, c_i \neq 0~ nếu phép tính của cửa đó là phép chia
• Bộ test đảm bảo kết quả không vượt quá kiểu dữ liệu long long (in64_t)

Sample

Input #1

1 4
+ 3 + 5
- 6 - 7
+ 3 + 10
* 5 * 9

Output #1

90

Giải thích #1:

Cho mảng số nguyên ~A~ có ~n~ phần tử được nhập từ bàn phím. Một bộ ba hoàn hảo là tích có giá trị lớn của 3 phần tử ở các vị trí khác nhau trong mảng.

Bởi vì một mảng có thể có nhiều bộ ba hoàn hảo nên chúng tôi cần biết tích của chúng để dễ dàng kiểm tra. Hãy giúp LCOJ viết chương trình đưa ra tích của bộ ba hoàn hảo mà bạn tìm được.

Input

• Dòng 1 là số lượng phần tử của mảng ~n~
• Dòng tiếp theo là ~n~ số nguyên tương ứng là các phần tử của mảng

Biết rằng

• ~n \in N^*~ và  ~3 \le n \le 10^7~
• Các phần tử của mảng ~|A_{i}| \le 10^4~

Output

Tích lớn nhất mà bạn tìm được

Sample

Input #1

5
1 2 3 4 5

Output #1

60

Giải thích: Bộ ba hoàn hảo trong trường hợp này là ~(3, 4, 5)~.

Một hồ chứa lớn được xây dựng trên sông Hồng bằng cách sử dụng một con đập. Giả sử rằng hồ chứa là một hình hộp chữ nhật có kích thước (tính bằng đơn vị). Hồ chứa gồm nhiều bể. Hình ảnh dưới đây là một ví dụvề mặt cắt ngang của một hồ chứa rỗng theo kích thước chiều dài và chiều cao của nó:

Nước chảy vào từ cửa trên cùng bên trái vào hồ chứa. Các bể chứa trong hồ được xây dựng bằng tường. Mỗi bức tường dày một đơn vị (chiều rộng) và ngắn hơn chiều cao của hồ chứa.

Cho biết vị trí và chiều cao của các bức tường và đơn vị và thể tích ~K~ của nước chảy vào, nhiệm vụ của bạn là tìm ra bức tường cuối cùng mà nước chảy tràn qua.

Input

Đầu vào bao gồm một số tập dữ liệu. Dòng đầu tiên của đầu vào chứa số lượng tập dữ liệu, là một số dương và không lớn hơn 20. Các dòng sau mô tả các tập dữ liệu.

Mỗi tập dữ liệu được mô tả bằng các dòng sau:

• Dòng đầu tiên là 1 số nguyên dương ~N~ - số lượng các bức tường ngăn cách các bể (~N \le 10^5~)
• Dòng thứ 2 chứa ~N~ số nguyên dương ~L_i~ -vị trí nằm ngang (dọc theo kích thước chiều dài của hồ chứa) của bức tường thứ ~i (1 \le L_i \le 10^9, L_i \gt L_{i-1} + 1\ \forall{i} > 1)~.
• Dòng thứ 3 chứa ~N~ số nguyên dương ~H_i~ - chiều cao của bức tường thứ ~i (1 \le H_i \le 10^5)~.
• Dòng thứ tư là một số nguyên ~Q (1 \le Q \le 10^5)~.
• Tại ~Q~ dòng tiếp theo, mỗi dòng là một số nguyên dương ~K~ cho biết thể tích nước chảy vào trong hồ chứa (~1 \le K \le 10^{15}~).

Giới hạn:

• 50% bộ test có ~T \le 10, N \le 1000, Q \le 1000~.
• 30% bộ test có ~T \le 20, N \le 10000, Q \le 10000~.
• 20% bộ test không có ràng buộc gì thêm.

Output

Với mỗi tập dữ liệu, in ra ~Q~ dòng tương ứng ~Q~ truy vấn. Dòng thứ ~i~ trả lời truy vấn thứ ~i~ là chỉ số của bức tường cuối cùng mà nước chảy tràn qua. Nếu nước không chảy tràn qua bức tường nào, in ra ~0~.

Sample

Input #1

1
4
1 3 5 8
2 5 3 1
3
3
13
17

Output #1

1
1
3

Hint

Hình ảnh dưới đây giải thích cho dữ liệu mẫu phía trên.

Problem source: ACM ICPC Asia Nha Trang Regional Contest 2016