Cho các số nguyên không âm \(a_1, b_1, a_2, b_2, a_3, b_3\). Hãy đếm số bộ ba \((x, y, z)\) thỏa mãn:

• \(a_1 \leq x \leq b_1\)
• \(a_2 \leq y \leq b_2\)
• \(a_3 \leq z \leq b_3\)
• \(x \times y = z\).

Input

• Dòng đầu tiên chứa 6 số nguyên không âm \(a_1, b_1, a_2, b_2, a_3, b_3\), các số có giá trị không vượt quá \(10^9\).

Output

• Ghi ra một số duy nhất là số bộ thỏa mãn đếm được.

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(b_1, b_2, b_3 \leq 300\);
• Subtask \(2\) (\(12\%\) số điểm): \(b_1, b_2, b_3 \leq 3000\);
• Subtask \(3\) (\(20\%\) số điểm): \(b_1, b_2, b_3 \leq 10^5\);
• Subtask \(4\) (\(20\%\) số điểm): \(b_1, b_2, b_3 \leq 10^7\);
• Subtask \(5\) (\(16\%\) số điểm): \(a_1 = b_1\);
• Subtask \(6\) (\(24\%\) số điểm): không có ràng buộc gì thêm.

Example

6 8 4 5 27 35 

4

Trên một trục đường dài thẳng có \(n\) trạm xe buýt cách đều nhau, các trạm được đánh số từ \(1\) đến \(n\). Để đi lại giữa hai trạm liên tiếp bất kì bằng xe buýt mất \(a\) đồng. Trong \(n\) trạm có \(m\) trạm đặc biệt là các trạm \(p_1, p_2, ..., p_m (1 \leq p_1, p_2, \dots , p_m \leq n)\). Có loại xe buýt nhanh sẽ chỉ dừng đỗ tại các trạm đặc biệt này, nếu sử dụng xe buýt nhanh để đi từ trạm đặc biệt \(p_i\) đến trạm đặc biệt \(p_j\) sẽ mất \(b\) x \(|p_i - p_j|\) đồng.

Yêu cầu: Cho \(q\) câu hỏi, câu hỏi thứ \(k\) \((1 \leq k \leq q)\) cần trả lời đi từ trạm \(x_k\) \((1 \leq x_k \leq n)\) tới trạm \(y_k\) \((1 \leq y_k \leq n)\) hết ít nhất bao nhiêu tiền.

Input

• Dòng đầu chứa các số nguyên dương \(n, m, q, a, b\) \((a, b \leq 10^6; 2 \leq m \leq n);\)
• Dòng thứ hai chứa \(m\) số nguyên dương \(p_1, p_2, \dots, p_m;\)
• Dòng thứ \(k\) \((1 \leq k \leq q)\) chứa hai số nguyên dương \(x_k, y_k\).

Output

• Ghi ra thiết bị ra chuẩn gồm \(q\) dòng, dòng thứ \(k\) chứa một số là câu trả lời cho câu hỏi thứ \(k\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m, q \leq 100; a = b\)
• Subtask \(2\) (\(25\%\) số điểm): \(n, m \leq 100; m = 2; p_1 = 1; p_2 = n\)
• Subtask \(3\) (\(25\%\) số điểm): \(n, m, q \leq 100\)
• Subtask \(4\) (\(25\%\) số điểm): \(n, m, q \leq 10^6\).

Example

5 2 2 2 1
2 4
1 5
2 3 

6
2

Cho dãy số nguyên \(A = (a_1, a_2, ..., a_n)\). Với hai số nguyên dương \(l, r(1 \leq l \leq r \leq n)\), gọi trọng số của cặp \((l, r)\) là tổng giá trị của các phần tử liên tiếp từ \(l\) đến \(r\) của dãy \(A\).

Yêu cầu: Cho dãy A và số nguyên k, hãy chọn ra k cặp \((l_1, r_1), (l_2, r_2), ..., (l_k, r_k)\) thõa mãn:

• \(1 \leq l_i \leq r_i \leq n\)
• Các cặp này đôi một khác nhau
• \(X \leq r_i - l_i + 1\)
• Tổng trọng số của \(k\) cặp đã chọn là lớn nhất

Input

• Dòng đầu chứa ba số nguyên dương \(n, k, X\)
• Dòng thứ hai chứa n số nguyên \(a_i (|a_i| \leq 10^5)\)

Output

• Ghi ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100; k \leq 1000\)
• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 1000; k \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^4; k \leq 10^4\)
• Subtask \(4\) (\(20\%\) số điểm): \(n, k \leq 5 \cdot 10^4\)
• Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 3 \cdot 10^5\)
• Subtask \(6\) (\(15\%\) số điểm): \(n \leq 3 \cdot 10^5; k \leq 10^7\).

Example

4 4 2
3 2 -6 8 

18