Bài tập

Linh là một học sinh rất yêu thích lập trình. Gần đây, Linh đang phát triển một robot có thể phân tích chuỗi số và tìm các đoạn "dễ thương".

Cụ thể, một đoạn con liên tiếp \((l, r)\) của dãy \(A_1, A_2, \ldots, A_n\) được gọi là dễ thương nếu:

• \(max - min = k\), với \(max\) là giá trị lớn nhất và \(min\) là giá trị nhỏ nhất trong đoạn đó.

Linh muốn bạn giúp đếm xem trong dãy ban đầu có tất cả bao nhiêu đoạn con dễ thương.

\InputFile

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le n \le 5 \times 10^5\), \(0 \le k \le 10^9\)).
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(-10^9 \le A_i \le 10^9\)).

\OutputFile

In ra một số nguyên duy nhất --- số lượng đoạn con dễ thương trong dãy.

\Scoring

• Subtask 1 (40% số điểm): \(n \le 10^3\).
• Subtask 2 (30% số điểm): \(n \le 10^5\).
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 1 3 3

6

An thấy hai số nguyên bạn nào đó đã viết lên bảng nên đã nghĩ cách tạo ra các dãy số mới từ hai dãy đó.

Gọi dãy thứ nhất là \(A\) gồm \(n\) số nguyên dương : \(a_{1}, a_{2}, ..., a_{n}\); dãy thứ hai là \(B\) cũng có \(n\) số nguyên dương: \(b_{1}, b_{2}, ..., b_{n}\). An viết lên bảng \(n\) dãy mới dựa trên hai dãy đã cho bằng cách thực hiện như sau:

1. Dãy thứ nhất: thay số hạng \(a_{1}\) của dãy \(A\) bằng tổng \(a_{1} + b_{1}\), các số hạng còn lại của dãy mới tương ứng với các số hạng còn lại của dãy \(A\).

2. Dãy thứ hai: thay số hạng \(a_{2}\) của dãy \(A\) bằng tổng \(a_{2} + b_{2}\), các số hạng còn lại của dãy mới tương ứng với các số hạng còn lại của dãy \(A\).

3. Dãy thứ ba: thay số hạng \(a_{3}\) của dãy \(A\) bằng tổng \(a_{3} + b_{3}\), các số hạng còn lại của dãy mới tương ứng với các số hạng còn lại của dãy \(A\).

...

Lặp lại như vậy cho đến khi viết đủ \(n\) dãy mới.

Yêu cầu: Hãy tính tổng của tất cả các số hạng trong tất cả các dãy mà An đã viết ra.

Input

Vào từ tệp văn bản CAU2.INP gồm :

• Dòng đầu tiên chứa số nguyên \(n\) \((0 < n < 50000)\).

• Dòng thứ hai chứa \(n\) số hạng của dãy \(A\): \(a_{1}, a_{2}, ..., a_{n}\) \((1 \leq a_{i} \leq 1000, 1 \leq i \leq n)\).

• Dòng thứ hai chứa \(n\) số hạng của dãy \(B\): \(b_{1}, b_{2}, ..., b_{n}\) \((1 \leq b_{i} \leq 1000, 1 \leq i \leq n)\).

Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra tệp văn bản CAU2.OUT gồm :

Một dòng ghi một số là tổng của các số hạng của tất cả các dãy số mà An đã viết ra.

Example

3
4 1 5
7 2 3

42

Scoring

\(40\%\) số test tương ứng với \(40\%\) số điểm có \(1 \leq n \leq 5000\).

Cho các bộ ba số nguyên không âm \((a, b, c)\), hãy tính giá trị \(a^{b^c} \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a, b, c\) (\(0 \le a, b, c \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^{b^c} \pmod{10^9 + 7}\) tương ứng với mỗi bộ ba \((a, b, c)\) trong dữ liệu vào.

Example

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(n, b, c \leq 4\).
• Subtask \(2\) (\(30\%\) số điểm) : \(c = 1\).
• Subtask \(3\) (\(40\%\) số điểm) : không có ràng buộc gì thêm.

Vương quốc Byteland có \(N\) nút giao thông trọng điểm được đánh số từ \(1\) đến \(N\). Hệ thống đường cao tốc gồm \(M\) con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) nối nút giao thông \(X_i\) với \(Y_i\) (\(1 \le i \le M, 1 \le X_i, Y_i \le N\)) có phí đường bộ là \(Z_i\) (\(Z_i \le 10^6\)).

\begincenter

\endcenter

Ví dụ: Từ nút giao thông 1 đến nút giao thông 4 (như hình vẽ) có hai đường đi khác nhau: đường đi thứ nhất là \(1 \to 2 \to 4\) có tổng phí đường bộ là 30, đường đi thứ hai là \(1 \to 3 \to 4\) có tổng phí đường bộ là 35.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa \(K\) con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông \(S\) đến nút giao thông \(T\) sau khi được Quốc vương ban hành chính sách mới.

Input

• Dòng đầu ghi năm số nguyên dương \(N, M, K, S, T\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi ba số nguyên dương \(X_i, Y_i, Z_i\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Example

4 4 1 1 4
1 2 10
1 3 30
2 4 20
3 4 5

5 

Scoring

• Có 20% số điểm tương ứng \(1 < N, M \le 100000\) và \(K = 0\);
• Có 20% số điểm tương ứng \(1 < N \le 100, M \le 1000\) và \(K = 1\);
• Có 20% số điểm tương ứng với \(1 < N, M \le 100000\) và \(K = 1\);
• Có 40% số điểm tương ứng với \(100 < N, M \le 100000\) và \(1 < K \le 10\).