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

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

Một lớp học có \(n\) học sinh, các học sinh được đánh số từ 1 đến \(n\). Thầy giáo chủ nhiệm muốn chọn ra một nhóm bạn để tham gia một trò chơi, một trò chơi cần sự phối hợp nhịp nhàng giữa các thành viên trong nhóm. Là một giáo viên nhiều kinh nghiệm, thầy giáo chủ nhiệm đã biết được sự phối hợp của \(m\) cặp học sinh, một cặp học sinh \(i(1 \leq i \leq n)\) và học sinh \(j(1 \leq j \leq n)\) có sự phối hợp là giá trị \(c(i, j)\), điều này có nghĩa là nếu học sinh \(i\) và học sinh \(j\) cùng được chọn vào nhóm thì tổng sự phối hợp của nhóm sẽ được cộng giá trị \(c(i, j)\), biết rằng \(-10^9 \leq c(i, j) \leq 10^9\).

Yêu cầu: Cho \(n\) học sinh và \(m\) cặp học sinh mà thầy giáo chủ nhiệm đã biết, hãy giúp thầy giáo chủ nhiệm chọn ra một nhóm để tổng sự phối hợp của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, m\).
• Dòng thứ \(k(1 \leq k \leq m)\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(i_k, j_k, c(i_k, j_k)\).

Output

• Dòng đầu tiên chứa số nguyên \(s\) là số học sinh trong nhóm.
• Dòng thứ hai gồm số \(s\) là chỉ số các bạn học sinh được chọn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 200\) và giá trị \(c(i, j)\) chỉ nhận một trong hai loại giá trị \(1\) hoặc \(-10^9\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 200\)

** Cách tính điểm **

Có \(20\) test, mỗi test \(5.0\) điểm. Với mỗi test, gọi tổng sự phối hợp của nhóm do thí sinh tìm được là \(c, q\), là tổng sự phối hợp của nhóm trong lời giải của Ban giám khảo, nếu \(c \leq 0\) thí sinh sẽ được \(0\) điểm, ngược lại số điểm của thí sinh đạt được là \(5.0 \cdot min\left(1, \dfrac{c^3}{q^3}\right)\)

Example

5 4
1 5 1
1 2 -1
2 5 3
1 4 -1 

3
1 2 5