Vào một buổi sáng anh Bo sắp một đàn bò gồm n con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ i có khả năng sẽ vắt được ai lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 01 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng.... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Input Format

• Dòng thứ nhất là số nguyên là số lượng con bò.

• Dòng thứ hai gồm n số nguyên a1, a2,..., an là sản lượng sữa của các con bò.

Constraints

1\<=n\<=10^5; 1\<=a[i]\<=10^6

Output Format

Số nguyên xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Sample Input 0

4
4 4 4 4

Sample Output 0

10

Cho số nguyên dương \(n\) và dãy \(a\) gồm \(n\) số nguyên \(a_{1}, a_{2}, \dots, a_{n}\). Một dãy con liên tiếp của dãy số \(a\) có dạng \(a_{i}, a_{i+1}, \dots, a_{j}\) với \(1 \le i \le j \le n\), tổng dãy con liên tiếp \(a_{i}, a_{i+1}, \dots, a_{j}\) là \(a_{i} + a_{i+1} + \dots + a_{j}\).

Em hãy đếm số lượng dãy con liên tiếp của dãy số \(a\) đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương \(k\).

Input

Đọc vào từ file CHIAK.INP gồm:

• Dòng 1: Hai số nguyên dương \(n, k\) (\(n \le 10^6, k \le 10^9\)) cách nhau một khoảng trống.
• Dòng 2: Ghi \(n\) số nguyên \(a_{1}, a_{2}, \dots, a_{n}\) (\(|a_{i}| \le 10^9, i = 1 \dots n\)) là giá trị của các phần tử của dãy ban đầu.

Output

Ghi ra file CHIAK.OUT một số nguyên duy nhất là số lượng dãy con có tổng các phần tử chia hết cho \(k\).

Scoring

• Subtask 1: Có \(5/25\) test tương ứng \(1\) điểm với \(n \le 10^2\).
• Subtask 2: Có \(15/25\) test tương ứng \(3\) điểm với \(n \le 10^3\).
• Subtask 3: Có \(5/25\) test tương ứng \(1\) điểm với \(n \le 10^6\).

Example

5 3
2 -6 1 9 -3

7

Bạn được cho một mảng chứa \(n\) số nguyên dương.

Nhiệm vụ của bạn là chia mảng thành \(k\) đoạn con sao cho tổng lớn nhất trong một đoạn con là nhỏ nhất có thể.

Input

• Dòng đầu tiên của đầu vào chứa hai số nguyên \(n\) và \(k\) - kích thước của mảng và số đoạn con cần chia.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) - các phần tử của mảng.

Output

• In ra một số nguyên: tổng lớn nhất trong một đoạn con trong cách chia tối ưu.

Constraints

• \(1 \leq n \leq 2\times10^5\)
• \(1 \leq k \leq n\)
• \(1 \leq x_i \leq 10^9\)

Sample Test

Input:

5 3
2 4 7 3 5

Output:

8

Viết chương trình nhập vào mảng \(n\) số nguyên \(a_1, a_2, \dots, a_n\). Thực hiện \(m\) truy vấn trên mảng số nguyên này, mỗi truy vấn có dạng hai số nguyên \(L, R\) với ý nghĩa tính:

Input

• Dòng đầu tiên ghi hai số nguyên \(n, m\) \((1 \leq n, m \leq 10^6)\).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 1000)\).
• Tiếp theo là \(m\) dòng, mỗi dòng ghi hai số nguyên \(L, R\).

Output

• In ra \(m\) dòng, mỗi dòng là kết quả của truy vấn tương ứng.

6 3
3 1 2 5 6 4
1 4
2 2
4 6

11
1
15

Số nguyên dương \(d\) được gọi là ước của số nguyên dương \(N\) nếu \(N\) chia hết cho \(d\). Ví dụ: các
ước của \(9\) là \(1, 3\) và \(9;\) các ước của \(10\) là \(1, 2, 5\) và \(10\).

Yêu cầu: Cho hai số nguyên dương \(L\) và \(R\) \((L ≤ R)\). Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ \(L\) tới \(R\) \((\)bao gồm cả \(L\) và \(R)\).

Dữ liệu:

Gồm một dòng chứa hai số nguyên dương \(L\) và \(R\) \((1 ≤ L ≤ R ≤ 10^9).\)

Kết quả:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ \(L\) tới \(R\).

Subtasks

• Có \(20\%\) số test ứng với \(R ≤ 1000\);
• \(25\%\) số test khác ứng với \(R - L ≤ 1000\);
• \(25\%\) số test khác ứng với \(R ≤ 10^6\);
• \(30\%\) số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn \([9, 12]\) là:
\(1, 2, 3, 4, 5, 6, 9, 10, 11\) và \(12\) \((7\) và \(8\) không nằm trong danh
sách này vì cả \(9, 10, 11\) và \(12\) đều không chia hết cho \(7\) hoặc
\(8)\).

Ta có \(1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63\).

Input

7 7

Output

8

Giải thích

Các số là ước của \(7\) là \(1\) và \(7\). Ta có \(1 + 7 = 8\).