Cải cách giáo dục

Một năm học gồm $n$ ngày. Mỗi ngày học sinh học đúng một môn, và mỗi môn được học nhiều nhất một ngày. Có tất cả $m$ môn học; sau buổi học môn thứ $i$, học sinh nhận bài tập về nhà gồm không ít hơn $a_i$ và không nhiều hơn $b_i$ bài. Ngoài ra môn thứ $i$ còn có độ khó $c_i$.

Nhà trường tự lập thời khoá biểu sao cho thoả mãn đồng thời các điều kiện sau:

• Các môn trong thời khoá biểu được xếp theo thứ tự độ khó tăng ngặt.
• Gọi $x_i$ là số bài tập được giao trong ngày thứ $i$. Với mọi $i$ thoả $1<i\le n$, phải có $x_i=x_{i-1}+k$ hoặc $x_i=k·x_{i-1}$.
• Tổng số bài tập của cả $n$ ngày là lớn nhất có thể.

Hai môn khác nhau có thể có cùng độ khó, nhưng khi đó chúng không thể cùng xuất hiện trong thời khoá biểu vì độ khó phải tăng ngặt.

Hãy lập thời khoá biểu cho năm học tới, hoặc cho biết không tồn tại thời khoá biểu hợp lệ.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$: số ngày trong năm học, số môn học và tham số $k$.
• Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $a_i$, $b_i$, $c_i$: hai giới hạn về số bài tập và độ khó của môn thứ $i$. Các môn được đánh số từ $1$ đến $m$.

Dữ liệu ra

Nếu không tồn tại thời khoá biểu hợp lệ, in ra một dòng duy nhất chứa NO.

Ngược lại, dòng đầu in ra YES, sau đó là $n$ dòng mô tả thời khoá biểu: dòng thứ $i$ chứa hai số nguyên dương là chỉ số môn học trong ngày thứ $i$ và số bài tập về nhà được giao trong ngày đó.

Nếu có nhiều thời khoá biểu cùng đạt tổng số bài tập lớn nhất, in ra một thời khoá biểu bất kỳ.

Ràng buộc

• $1\le n\le m\le 50$
• $1\le k\le 100$
• $1\le a_i\le b_i\le {10}^{16}$
• $b_i-a_i\le 100$
• $1\le c_i\le 100$

Ví dụ