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 rất yêu thích tuyết. Trong \(n\) ngày, mỗi ngày Bình tạo ra một đống tuyết có thể tích \(v_i\).
Nhưng mỗi ngày, nhiệt độ \(t_i\) khiến mỗi đống tuyết (kể cả đống mới tạo) bị giảm đúng \(t_i\) đơn vị.
Đống tuyết nào giảm xuống \(\le 0\) thì biến mất.

Nhiệm vụ của bạn: Tính tổng thể tích tuyết bị tan chảy trong mỗi ngày.

Input

• Dòng 1: số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng 2: \(v_1, v_2, \dots, v_n\) (\(0 \le v_i \le 10^9\)).
• Dòng 3: \(t_1, t_2, \dots, t_n\) (\(0 \le t_i \le 10^9\)).

Output

Một dòng gồm \(n\) số --- lượng tuyết tan trong từng ngày.

Example

3
10 10 5
5 7 2

5 12 4

Scoring

• Subtask 1 (10%): \(t_i = 0\).
• Subtask 2 (30%): \(n, t_i, v_i \le 10^3\).
• Subtask 3 (60%): Không có ràng buộc thêm.

Một số nguyên dương \(X\) được gọi là số đẹp nếu:

• \(X > 1\)
• \(X\) có đúng \(3\) ước số nguyên dương.

Ví dụ:

• \(4\) có đúng \(3\) ước số là \(1, 2, 4\) nên \(4\) là số đẹp.
• \(9\) có \(3\) ước là \(1, 3, 9\) nên cũng là số đẹp.
• \(6\) có \(4\) ước là \(1, 2, 3, 6\) nên không phải là số đẹp.

Yêu cầu: Cho \(T\) truy vấn, với truy vấn thứ \(i\) \((1 \le i \le T)\), cho một số nguyên dương \(a_i\), hãy xác định có bao nhiêu số đẹp trong phạm vi từ \(1\) đến \(a_i\).

Input

Dữ liệu được đọc từ file SODEP.INP:

• Dòng đầu tiên chứa số nguyên \(T\) \((1 \le T \le 10^6)\) --- số truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(a_i\) \((1 \le a_i \le 10^6)\) --- giá trị truy vấn thứ \(i\).

Output

Ghi ra file SODEP.OUT \(T\) dòng, mỗi dòng là kết quả của truy vấn tương ứng: số lượng số đẹp từ \(1\) đến \(a_i\).

Example

2
10
50

2
4

Scoring

• \(30\%\) số test ứng với \(T = 1\), \(1 \le a_i \le 10^3\)
• \(40\%\) số test ứng với \(1 \le T \le 10^3\), \(1 \le a_i \le 10^6\)
• \(30\%\) số test ứng với \(1 \le T \le 10^6\), \(1 \le a_i \le 10^12\)

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.