Contest 08

Một số nguyên dương \(x\) được gọi là số đẹp nếu như tất cả các ước số của nó không phải là số chính phương lớn hơn \(1\).

Ví dụ: \(5\) là số đẹp vì \(2\) ước số \(1\) và \(5\) của nó không phải số chính phương lớn hơn \(1\), trong khi đó \(12\) không phải là số đẹp vì nó có ước số \(4\) là một số chính phương lớn hơn \(1\).

Cho một số nguyên dương \(n\), hãy tìm ước số \(d\) lớn nhất của \(n\) sao cho \(d\) là một số đẹp.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\).

Output

• Ghi ra một số nguyên là ước số \(d\) lớn nhất của \(n\) sao cho \(d\) là một số đẹp. Nếu không tồn tại ước số nào của \(n\) là số đẹp thì in ra \(-1\).

Example

10

10

12

6

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{12}\).

Cho \(T_k = 1 + 2 + \dots + k\) và \(S_n = T_1 + T_2 + \dots + T_n\).

Cho số nguyên dương \(n\) (\(n \leq 10^5\)). Hãy lập trình tính tổng \(S_n\).

Input

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

Output

• Một dòng duy nhất là giá trị của tổng \(S_n\).

Example

1

1

4

20

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(10 < n \leq 1000\).
• Subtask \(3\) (\(40\%\) số điểm): \(1000 < n \leq 10^5\).

Albert, Jade, Pearl là một nhóm "bạn thân" với mối quan hệ phức tạp: Jade crush Albert, Pearl crush Albert, còn Albert crush cả hai. Đặc biệt, Albert cũng biết rõ tình cảm của Jade và Pearl dành cho mình nên Albert luôn phải đau đầu vì không biết nên chọn ai. Nhưng nghĩ cho tương lai, Albert muốn con mình phải thật thông minh nên quyết định đố Jade và Pearl một bài toán. Ai giải được sẽ được làm người yêu Albert.

Đề bài như sau: Cho một dãy bit (dãy bit là một dãy số gồm các chữ số \(0\) và \(1\)), hãy tìm ra đoạn bit liên tiếp được ghép bởi dãy bit \(0\) liên tiếp với dãy bit \(1\) liên tiếp sao cho số chữ số \(0\) bằng số chữ số \(1\) và có độ dài lớn nhất.

Ví dụ: Cho dãy số bit 0100011100001100 thì đoạn bit thỏa mãn đề bài có độ dài lớn nhất là \(6\) (000111 hoặc 111000).

Biết trước đề, Jade tìm mọi cách để giải được bài toán đấy nhưng do không được học nên Jade mãi không làm ra. Bạn hãy giúp Jade giải bài toán này nhé!

Input

• Gồm một dòng duy nhất chứa dãy số bit có độ dài từ \(1\) đến \(10^6\).

Output

• Ghi ra một số nguyên duy nhất là độ dài lớn nhất thỏa mãn đề bài.

Example

100111000011111

8

Scoring

• Subtask \(1\) (\(40\%\) số điểm): Độ dài của đoạn bit nhỏ hơn hoặc bằng \(100\).
• Subtask \(2\) (\(30\%\) số điểm): Độ dài của đoạn bit nhỏ hơn hoặc bằng \(1000\).
• Subtask \(3\) (\(30\%\) số điểm): Độ dài của đoạn bit nhỏ hơn hoặc bằng \(10^6\).

Cho lưới ô vuông \(A\) kích thước \(M \times N\), trong đó các dòng được đánh thứ tự từ \(1\) đến \(M\) từ trên xuống dưới, các cột được đánh thứ tự từ \(1\) đến \(N\) từ trái sang phải, ô nằm trên dòng \(i\), cột \(j\) có chứa giá trị nguyên \(A[i, j]\).

Nhiệm vụ của bạn là tìm lưới ô vuông con (là hình chữ nhật nằm trong lưới đã cho) có tổng các phần tử trong đó là lớn nhất.

Input

• Dòng đầu tiên là hai số nguyên \(M\) và \(N\) (\(1 \le M, N \le 500\)).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số \(A_{i1}, A_{i2}, \dots, A_{iN}\) (\(|A_{ij}| \le 5 \cdot 10^4\)).
• Các số nằm trên cùng một dòng cách nhau ít nhất một dấu cách.

Output

• Một dòng duy nhất là tổng lớn nhất của các phần tử thuộc lưới ô vuông con tìm được.

Example

3 5
-4 5 -18 9 5
-16 4 0 -4 9
5 -1 4 -1 2

20

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(M, N \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(M, N \le 500\).