Bài tập

Trên một dải gồm \(N\) ô xếp thành hàng, ô thứ \(i\) (\(1 \le i \le N\)) chứa một số nguyên \(a_i\) (có thể âm). Quân cờ ban đầu nằm ở ô số \(0\) (ô xuất phát, không chứa giá trị) và tổng điểm bằng \(0\).

Mỗi lượt đi, quân cờ tiến sang phải ít nhất \(1\) và nhiều nhất \(K\) ô. Mỗi khi hạ cánh xuống ô \(i\), giá trị \(a_i\) được cộng vào tổng điểm (các ô bị nhảy qua không được tính). Người chơi có thể dừng lại tại bất kỳ thời điểm nào, kể cả khi chưa đi lượt nào (khi đó điểm là \(0\)), nhưng không được đi ra ngoài ô \(N\).

Hãy tính tổng điểm lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra một số nguyên: tổng điểm lớn nhất.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le K \le 100\)
• \(-10^9 \le a_i \le 10^9\)

Sample Input

7 3
-4 2 -7 -5 -6 8 -1

Sample Output

5

Explanation

Đi theo các ô \(2 \to 4 \to 6\) (mỗi lượt bước không quá \(3\) ô) thu được \(2 + (-5) + 8 = 5\). Sau đó dừng lại. Không có cách nào tốt hơn.

Một phi thuyền xuất phát tại toạ độ \(K\) trên một trục số. Mỗi lần "nhảy", phi thuyền có thể dịch chuyển đến một trong bốn vị trí: \(x + d_1\), \(x - d_1\), \(x + d_2\) hoặc \(x - d_2\) (với \(x\) là vị trí hiện tại). Phi thuyền có thể nhảy bao nhiêu lần tuỳ ý và đi qua các toạ độ nguyên bất kỳ, kể cả toạ độ âm.

Trên trục có \(N\) hành tinh, hành tinh thứ \(i\) ở toạ độ \(X_i\). Một hành tinh được xem là thăm được nếu phi thuyền có thể đáp xuống đúng toạ độ đó (nếu \(X_i = K\) thì không cần nhảy).

Hãy đếm số hành tinh thăm được.

Input

• Dòng đầu chứa bốn số nguyên \(N, K, d_1, d_2\).
• Dòng thứ hai chứa \(N\) số nguyên \(X_1, \dots, X_N\).

Output

In ra một số nguyên: số hành tinh thăm được.

Constraints

• \(1 \le N \le 10^5\).
• \(|K| \le 10^9\).
• \(1 \le d_1, d_2 \le 10^9\).
• \(-10^9 \le X_i \le 10^9\).

Sample Input

5 3 6 9
0 6 7 -6 12

Sample Output

4

Explanation

Từ toạ độ \(3\) với các bước \(6\) và \(9\), phi thuyền chỉ đến được những toạ độ có hiệu với \(3\) chia hết cho \(3\). Các toạ độ \(0, 6, -6, 12\) thoả mãn, còn \(7\) thì không.

Cho dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(S\). Hãy đếm số bộ có thứ tự bốn chỉ số \((i, j, k, l)\) với \(1 \le i, j, k, l \le N\) (các chỉ số được phép trùng nhau) sao cho

Hai bộ là khác nhau nếu chúng khác nhau ở ít nhất một vị trí trong bốn vị trí chỉ số. Đáp án có thể rất lớn (tối đa vào cỡ \(10^{24}\)), hãy in ra chính xác.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(S\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

In ra một số nguyên: số bộ chỉ số thoả mãn.

Constraints

• \(1 \le N, S \le 10^6\).
• \(1 \le A_i \le 10^6\).
• Các subtask: (40%) \(N \le 100\); (20%) \(N \le 1000\); (20%) \(N \le 10^5\); (20%) không ràng buộc thêm.

Sample Input 1

5 20
1 4 2 2 3

Sample Output 1

28

Sample Input 2

6 10
1 3 3 2 1 2

Sample Output 2

96

Explanation

Gọi \(c_v\) là số cặp chỉ số có thứ tự \((i, j)\) với \(A_i \cdot A_j = v\). Khi đó đáp án bằng \(\sum_{v=1}^{S-1} c_v \cdot c_{S-v}\). Ở ví dụ 1 tổng này bằng \(28\); ở ví dụ 2 bằng \(96\).

Bé Na vừa được tặng một chiếc máy tính bỏ túi nhưng chỉ có bốn phím phép tính. Cho hai số nguyên \(A\) và \(B\), hãy in ra kết quả của bốn phép: cộng, trừ, nhân, chia \(A\) cho \(B\).

Input

• Dòng thứ nhất: số nguyên \(A\).
• Dòng thứ hai: số nguyên \(B\).

Dữ liệu được đọc từ bàn phím (standard input).

Output

In ra đúng \(4\) dòng theo mẫu, mỗi dòng viết các số đúng như đã cho (số âm giữ nguyên dấu trừ), dùng dấu - thông thường cho phép trừ:

A + B = tổng
A - B = hiệu
A * B = tích
A : B = thương

Thương \(A : B\) được làm tròn đến \(2\) chữ số sau dấu phẩy theo quy tắc thông thường (phần thập phân đúng bằng \(5\) ở chữ số thứ ba thì làm tròn ra xa số \(0\), ví dụ \(-0.875\) thành \(-0.88\)). Nếu sau khi làm tròn giá trị bằng \(0\) thì in 0.00 (không có dấu trừ).

Constraints

• \(|A|, |B| \le 10^9\)
• \(B \ne 0\)

Sample Input

17
5

Sample Output

17 + 5 = 22
17 - 5 = 12
17 * 5 = 85
17 : 5 = 3.40