Chuyến đi Saint Petersburg

Bạn đang lên kế hoạch cho chuyến đi tới Saint Petersburg. Mỗi ngày ở lại trong thành phố bạn phải tiêu tốn $k$ rúp. Nếu ngày tới là $L$ và ngày về là $R$ ($L\le R$), tổng chi phí của chuyến đi là $k·(R-L+1)$ rúp.

Để bù lại chi phí, bạn có thể nhận làm các dự án ngay tại Saint Petersburg. Có $n$ dự án, dự án thứ $i$ kéo dài từ ngày $l_i$ đến ngày $r_i$ (bao gồm cả hai đầu mút). Nếu tham gia dự án $i$, bạn phải có mặt ở Saint Petersburg trong toàn bộ khoảng thời gian đó (tức là $L\le l_i$ và $R\ge r_i$), và sẽ nhận về $p_i$ rúp khi hoàn thành.

Bạn có thể nhận bao nhiêu dự án tuỳ ý, kể cả các dự án có thời gian chồng nhau, mà không bị giới hạn năng lực.

Hãy chọn ngày tới $L$, ngày về $R$ và tập dự án $S$ sao cho:

• $R\ge L$;
• Mọi dự án $s\in S$ đều thoả $L\le l_s$ và $R\ge r_s$;
• Tổng lợi nhuận ${\displaystyle {\sum }_{s\in S}{p}_s-k·(R-L+1)}$ là một số dương và đạt giá trị lớn nhất có thể.

Nếu không thể có chuyến đi với lợi nhuận dương, in ra số $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ ($1\le n\le 2·{10}^5$, $1\le k\le {10}^{12}$).
• $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $l_i$, $r_i$, $p_i$ ($1\le l_i\le r_i\le 2·{10}^5$, $1\le p_i\le {10}^{12}$).

Dữ liệu ra

• Nếu không thể đạt được lợi nhuận dương, in ra một dòng duy nhất chứa số $0$.
• Ngược lại, in ra hai dòng:
  • Dòng đầu chứa bốn số nguyên $p$, $L$, $R$, $m$ — lợi nhuận lớn nhất, ngày tới, ngày về và số dự án được chọn.
  • Dòng thứ hai chứa $m$ số nguyên phân biệt là chỉ số các dự án được chọn (theo thứ tự bất kỳ).
• Nếu có nhiều phương án cùng đạt lợi nhuận lớn nhất, in ra một phương án bất kỳ.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le k\le {10}^{12}$
• $1\le l_i\le r_i\le 2·{10}^5$
• $1\le p_i\le {10}^{12}$

Ví dụ