2023 · HSG THCS · Khánh Hòa

Bình là một học sinh lớp ~1~ rất nghịch. Em lấy kéo cắt một tờ giấy hình chữ nhật ra thành các mảnh nhỏ. Bình cắt theo chiều song song với các cạnh của hình chữ nhật (từ trái qua phải hoặc từ trên xuống dưới).

Yêu cầu bài toán như sau: Cho số lần cắt của Bình là ~n~, tính số mảnh hình chữ nhật được tạo ra nhiều nhất có thể sau ~n~ lần cắt.

Hãy viết chương trình nhập vào số ~n~ là số lần cắt của Bình. In ra màn hình số lượng mảnh giấy nhiều nhất có thể.

Input

Vào từ bàn phím:

• Một số nguyên ~n~ với ~1 \leq n \leq 10^6~.

Output

In ra màn hình:

• Một số nguyên dương duy nhất là kết quả bài toán.

Example input 1

3

Example output 1

6

Note 1

• Với ~n = 3~, số mảnh hình chữ nhật nhiều nhất có thể tạo ra là ~6~.

An có ~r~ quả táo màu đỏ và ~g~ quả táo màu xanh để cho những người bạn của An. Nhưng khi chia thì tất cả các người bạn nhận số táo đỏ và táo xanh là giống nhau.

Yêu cầu: Hãy viết chương trình đưa ra tất cả các cách chia táo.

Input

Vào từ file văn bản CHIATAO.INP:

• Ghi lần lượt hai số nguyên ~r~ và ~g~ trên một dòng; ~1 \leq r, g \leq 10^9~.

Output

Ghi ra file văn bản CHIATAO.OUT:

• Ghi trên nhiều dòng, mỗi dòng ghi ~3~ số nguyên ~n~, ~x~, ~y~ cho biết một cách chia táo.

  • ~n~ là số người bạn sẽ được nhận táo,
  • ~x~ là số táo đỏ mỗi người nhận được,
  • ~y~ là số táo xanh mỗi người nhận được.

Example input 1

4 8

Example output 1

1 4 8
2 2 4
4 1 2

Note 1

• Trong ví dụ, có ~3~ cách chia tương ứng với các giá trị ~n~ khác nhau.

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Input

Vào từ file văn bản SUBSEQ.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên dương ~n~ với ~n \leq 10^6~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi số nguyên ~a_i~ với ~|a_i| \leq 10^8~.

Output

Ghi ra file văn bản SUBSEQ.OUT theo quy định:

• Dòng đầu ghi vị trí của phần tử đầu tiên của dãy tìm được.
• Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được.
• Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.
• Nếu có nhiều tổng lớn nhất bằng nhau, ưu tiên đoạn con ngắn nhất và ở trước.

Example input 1

8
12
-14
1
23
-6
22
-34
13

Example output 1

3
6
40

Trên một nền phẳng đã được chia thành các lưới ô vuông đơn vị gồm ~m \times n~ ô, trong đó ~0 < m, n \leq 100~, người ta đặt chồng khít lên nhau các khối lập phương đơn vị tạo thành những cột. Khối dưới cùng của một cột chiếm trọn ô của lưới. Chiều cao của mỗi cột được tính bằng số khối lập phương đơn vị tạo thành cột đó. Sau khi xếp xong toàn bộ các cột, người ta tiến hành sơn các mặt nhìn thấy được của các cột.

Yêu cầu: Cho biết chiều cao của mỗi cột, hãy tính số đơn vị diện tích cần sơn.

Input

Vào từ file văn bản PAINT.INP:

• Dòng đầu tiên ghi hai số nguyên dương ~m~, ~n~ (~m~ hàng, ~n~ cột) là kích thước của lưới nền.
• ~m~ dòng tiếp theo, dòng thứ ~i~ ghi ~n~ số nguyên không âm; số nguyên thứ ~j~ biểu thị chiều cao của cột dựng tại ô ~(i,j)~ của lưới.

Output

Ghi ra file văn bản PAINT.OUT:

• Một số nguyên cho biết diện tích cần sơn.

Example input 1

2 3
4 3 4
1 2 1

Example output 1

42