Cho dãy ~n~ số nguyên ~a_1, a_2, …, a_n~ và một số nguyên ~k~. Mức độ đẹp của một dãy con liên tiếp ~a_i, a_{i+1}, …, a_j~ được đánh giá bằng ~GCD(a_i, a_{i+1}, …, a_j).(a_i + a_{i+1} + … + a_j)~, tức là độ đẹp bằng ước chung lớn nhất của các phần tử trong dãy con nhân với tổng các phần tử trong dãy con đó.

Yêu cầu: Tìm dãy con liên tiếp có ít nhất ~k~ phần tử và có mức độ đẹp là lớn nhất.

Input

• Dòng 1: Hai số nguyên ~n, k\ (1 ≤ k ≤ n ≤ 10^6)~;
• Dòng 2: ~n~ số nguyên ~a_1, a_2, …, a_n\ (1 ≤ a_i ≤ 10^6)~.

Output

• Ghi ra một số nguyên duy nhất là mức độ đẹp tìm được.

Subtask

• 10% số điểm tương ứng với 10% số test có ~n, k ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5000~;
• 25% số điểm tương ứng với 25% số test có ~a_i ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5.10^4~;
• 25% số điểm tương ứng với 25% số test không có ràng buộc gì thêm

Example

Sample Input

6 2
4 4 4 3 1 3

Sample Output

48

Có ~n~ đồ vật được đánh số từ ~1~ tới ~n~. Đồ vật thứ ~i~ có trọng lượng là ~w_i~ và có giá trị là ~v_i~.

Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ gồm ba số nguyên ~l_i~, ~r_i~ , ~W_i~, hỏi rằng giả sử nếu chỉ xét các đồ vật trong đoạn ~[l_i,r_i]~, thì với tổng trọng lượng tối đa là ~W_i~, bạn có thể thu được tổng giá trị lớn nhất là bao nhiêu? Biết rằng mỗi đồ vật trong đoạn đó bạn chỉ có thể lấy tối đa một lần.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương miêu tả đồ vật thứ ~i~: ~w_i~ và ~c_i~ ~(1 \le w_i \le 100, c_i \le 10^4)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ miêu tả số truy vấn ~(q \le 10^5)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương miêu tả truy vấn thứ ~i~: ~l_i~, ~r_i~, ~W_i~ ~(1 \le l_i \le r_i \le n; 1 \le W_i \le 100)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask ~1~: ~r-l \le 100~ ~(40\%)~
• Subtask ~2~: ~q \le 10^4~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4
2 15
2 20
4 36
1 4
3
1 2 4
1 4 7
3 4 2

Sample Output 1

35
60
4

Cho một cây có trọng số gồm ~n~ đỉnh được đánh số từ ~1~ tới ~n~. Đỉnh ~u~ đang có ~p_u~ người. Cạnh nối giữa hai đỉnh ~u~ và ~v~ có trọng số là ~d(u,v)~.

Bạn có một phương tiện có thể di chuyển một lúc tối đa ~c~ người trong một chuyến. Đồng nghĩa với việc, để di chuyển ~x~ nhân viên từ hai đỉnh ~u~ và ~v~ kề với nhau thì sẽ tốn chi phí là ~\lceil \frac{x}{c} \rceil \times d(u,v)~.

Nhiệm vụ của bạn là tính ra tổng chi phí bé nhất để di chuyển mọi người sao cho số lượng người chênh lệch giữa các đỉnh trên cây là nhỏ nhất. Nói cách khác, gọi ~Max~ là số người nhiều nhất trên một đỉnh của cây sau khi di chuyển, tương tự ~Min~ là số người ít nhất, bạn cần tối ưu ~Max - Min~ bé nhất có thể.

Input

• Dòng đầu gồm hai số nguyên dương ~n~ và ~c~ ~(1 \le n \le 2000, 1 \le c \le 10^6)~
• Dòng thứ hai gồm ~n~ số nguyên không âm ~p_1, p_2, ..., p_n~ miêu tả số người trên mỗi đỉnh.
• ~n-1~ dòng cuối cùng, dòng thứ ~i~ gồm ba số nguyên ~u_i,v_i, d(u_i,v_i)~ miêu tả cạnh thứ ~i~ ~(1 \le u_i \le v_i \le n, 1 \le d(u_i,v_i) \le 10^6)~.

Output

• In ra tổng chi phí nhỏ nhất có thể để thỏa mãn yêu cầu đề bài.

Subtask

• Subtask ~1~: ~n = 3~ ~(20\%)~
• Subtask ~2~: ~n,c \le 100~ ~(30\%)~
• Subtask ~3~: Cây là đường thẳng ~(20\%)~
• Subtask ~4~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4 10
12 9 36 28
1 2 1
1 3 1
2 4 2

Sample Output 1

5

Có ~N+2~ thị trấn xếp thẳng hàng. Các thị trấn được đánh số từ ~0~ đến ~N+1~ từ trái sang phải. Mỗi thị trấn ~i~ ~(1 \leq i \leq N)~ có một nơi trú ẩn có thể chứa tối đa ~A_i~ người.

Hiện tại, có ~S~ người đang di chuyển cùng nhau và ghé thăm một trong các thị trấn. Tuy nhiên, bạn không biết họ đang ghé thăm thị trấn nào.

Bạn vừa nhận được thông tin có ~Q~ thiên thạch có thể rơi xuống các thị trấn. Thiên thạch thứ ~i~ có thể rơi vào các thị trấn từ ~L_i, L_i+1, \cdots, R_i~. Để đảm bảo an toàn cho người đi đường, đối với mỗi thiên thạch, bạn cần tính chi phí sơ tán mà chính quyền cần bỏ ra.

Chi phí sơ tán cho một thiên thạch được tính như sau:

• Chi phí sơ tán là tổng chi phí tối thiểu cần thiết để đảm bảo tất cả người đi đường được an toàn bất kể họ đang ở thị trấn nào.
• Một người được coi là an toàn nếu người đó ở trong một nơi trú ẩn hoặc ở một thị trấn nằm ngoài khu vực ảnh hưởng của thiên thạch (vậy thì người đó sẽ không cần vào nơi trú ẩn ở thị trấn đó).
• Mỗi người cần ~1~ đơn vị chi phí để di chuyển đến thị trấn liền kề (hai thị trấn được coi là liền kề nếu chỉ chênh lệch nhau đúng ~1~ đơn vị số thứ tự).

Lưu ý rằng chỉ di chuyển người mới tốn chi phí, và các hành động khác (như cho người vào nơi trú ẩn) không tốn chi phí. Đảm bảo rằng các thị trấn ~0~ và ~N+1~ sẽ không bao giờ bị ảnh hưởng bởi thiên thạch, vì vậy luôn có cách để đảm bảo tất cả người đi đường an toàn.

Input

Dữ liệu được cho theo định dạng sau

~N~ ~S~

~A_1 A_2 ⋯ A_N~

~Q~

~L_1~ ~R_1~

~L_2~ ~R_2~

⋮

~L_Q~ ~R_Q~

Ràng buộc

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq S \leq 10^{12}~
• ~0 \leq A_i \leq S~
• ~A_1 + A_2 + ⋯ + A_N \leq 10^{12}~
• ~1 \leq Q \leq 2 \times 10^5~
• ~1 \leq L_i \leq R_i \leq N~

Tất cả các giá trị trong đầu vào đều là số nguyên.

Subtask

• Subtask ~1~: ~n,q \le 100~ ~(20\%)~
• Subtask ~2~: ~n,q \le 2000~ ~(20\%)~
• Subtask ~3~: ~L_i = 1~ ~(30\%)~
• Subtask ~4~: Không giới hạn gì thêm ~(30\%)~

Output

• In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Example

Sample Input 1

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

Sample Output 1

13
4
15

Explanation

Ở truy vấn ~1~, nếu nhóm người đang ở thành phố ~3~ thì sẽ mất tổng số chi phí là ~13~.

Ở truy vấn ~2~, ~4~ người không có chỗ trú ẩn có thể đi hết sang thành phố ~6~ để thoát khỏi nguy hiểm.