Trong bài tập này, ta có một con đường có thể được biểu diễn dưới dạng trục tọa độ 1D. Trên con đường có \(n\) biển báo. Các biển báo được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái qua phải. Biển báo thứ \(i\) đặt tại điểm có tọa độ \(x_i\) và trên đó có ghi hai số \(a_i\) và \(b_i\). Vị trí của các biển báo thỏa mãn \(x_1 < x_2 < \cdots < x_n\).

Bạn cần chọn ra một đoạn liên tiếp các biển báo \([u..v]\) cùng hai điểm đặc biệt \(L\) và \(R\) trên trục số sao cho:

Với mọi biển báo \(i\) thuộc đoạn \([u..v]\) (tức \(u \le i \le v\)), ít nhất một trong hai điều dưới đây là đúng:

• \(x_i - a_i = L\)
• \(x_i + b_i = R\)

Số biển báo thuộc đoạn \([u..v]\) là nhiều nhất có thể.

Ngoài ra, bạn cần đếm số cách chọn đoạn \([u..v]\) và hai điểm \(L\) và \(R\) thỏa mãn các điều kiện trên.

Chú ý rằng, hai điểm \(L\) và \(R\) có thể là các điểm bất kỳ trên trục số, bao gồm cả điểm có tọa độ âm, tọa độ không phải số nguyên hay điểm trùng với vị trí của biển báo. Hai điểm này cũng có thể trùng nhau. Hai cách chọn được gọi là khác nhau khi đoạn \([u..v]\) được chọn khác nhau, điểm \(L\) khác nhau hoặc điểm \(R\) khác nhau.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 4 \cdot 10^5)\) là số biển báo.
• Trong \(n\) dòng còn lại, dòng thứ \(i\) chứa ba số nguyên \(x_i\) \((-10^8 \le x_i \le 10^8)\), \(a_i\) và \(b_i\) \((1 \le a_i, b_i \le 10^8)\).
• Dữ liệu vào đảm bảo \(x_1 < x_2 < \cdots < x_n\).

Output

• In ra trên một dòng hai số nguyên, lần lượt là giá trị lớn nhất của số biển báo thuộc đoạn \([u..v]\) và số cách chọn đoạn \([u..v]\) cùng hai điểm \(L\) và \(R\).
• Nếu có nhiều hơn \(2^{271997}\) cách chọn, in ra \(-1\).

Example

5
3 1 5
4 2 4
5 2 2
6 5 3
7 6 2

3 4

Scoring

• Subtask \(1\) (\(7\) điểm): \(a_1 = a_2 = \cdots = a_n\) và \(b_1 = b_2 = \cdots = b_n\)
• Subtask \(2\) (\(15\) điểm): \(b_1 = b_2 = \cdots = b_n\)
• Subtask \(3\) (\(16\) điểm): \(n \le 300\)
• Subtask \(4\) (\(18\) điểm): \(n \le 10000\)
• Subtask \(5\) (\(14\) điểm): Không có ràng buộc gì thêm.