Chuẩn bị tiệc 2

Đầu bếp vừa nấu xong $n$ món ăn: món thứ $i$ gồm $a_i$ gam cá và $b_i$ gam thịt.

Ban tổ chức tiệc coi hai món $i$ và $j$ là giống nhau nếu đồng thời $a_i=a_j$ và $b_i=b_j$ (cùng lượng cá và cùng lượng thịt). Độ đa dạng của một tập món ăn là số lượng món khác nhau trong tập đó. Độ đa dạng càng nhỏ càng tốt.

Để giảm độ đa dạng, một người nếm thử được mời đến. Với mỗi món, anh ta sẽ ăn đúng $m_i$ gam thức ăn. Với từng món, anh ta tự quyết định ăn bao nhiêu gam cá và bao nhiêu gam thịt, miễn sao tổng lượng ăn từ món $i$ đúng bằng $m_i$ gam. Nghĩa là nếu anh ăn $x_i$ gam cá và $y_i$ gam thịt từ món $i$ thì phải có $0\le x_i\le a_i$, $0\le y_i\le b_i$ và $x_i+y_i=m_i$.

Sau khi ăn, món $i$ còn lại $(a_i-x_i)$ gam cá và $(b_i-y_i)$ gam thịt. Hãy xác định người nếm thử nên ăn bao nhiêu cá và bao nhiêu thịt từ mỗi món để độ đa dạng của các món còn lại là nhỏ nhất có thể. Nếu có nhiều cách, in ra một cách bất kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu được phân tách với bộ trước bởi một dòng trống, rồi đến một dòng chứa số nguyên $n$ — số món ăn; tiếp theo là $n$ dòng, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $m_i$.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Dòng đầu in độ đa dạng nhỏ nhất đạt được.
• Tiếp theo in $n$ dòng, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ ($0\le x_i\le a_i$; $0\le y_i\le b_i$; $x_i+y_i=m_i$) — số gam cá và số gam thịt người nếm thử ăn từ món $i$.

Nếu có nhiều cách đạt giá trị nhỏ nhất, in ra cách bất kỳ.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 2·{10}^5$
• $0\le a_i,b_i\le {10}^6$
• $0\le m_i\le a_i+b_i$
• Tổng tất cả các giá trị $n$ trên mọi bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ