CF1607H.Banquet Preparations 2

The chef has cooked $n$ dishes yet again: the $i$-th dish consists of $a_i$ grams of fish and $b_i$ grams of meat.

Banquet organizers consider two dishes $i$ and $j$ equal if $a_i=a_j$ and $b_i=b_j$ at the same time.

The banquet organizers estimate the variety of $n$ dishes as follows. The variety of a set of dishes is equal to the number of different dishes in it. The less variety is, the better.

In order to reduce the variety, a taster was invited. He will eat exactly $m_i$ grams of food from each dish. For each dish, the taster determines separately how much fish and how much meat he will eat. The only condition is that he will eat exactly $m_i$ grams of the $i$-th dish in total.

Determine how much of what type of food the taster should eat from each dish so that the value of variety is the minimum possible. If there are several correct answers, you may output any of them.

厨师再次烹制了 $n$ 道菜肴：第 $i$ 道菜肴由 $a_i$ 克鱼肉和 $b_i$ 克猪肉组成。

宴会组织者认为两道菜肴 $i$ 和 $j$ 相等，当且仅当同时满足 $a_i = a_j$ 且 $b_i = b_j$。

宴会组织者按如下方式评估这 $n$ 道菜肴的多样性：一道菜肴集合的多样性等于其中互不相同的菜肴数量。多样性越小越好。

为降低多样性，主办方邀请了一位品鉴师。他将从每道菜肴中恰好吃掉 $m_i$ 克食物。对于每道菜肴，品鉴师可自行决定分别吃掉多少克鱼肉和多少克猪肉，唯一约束是：他从第 $i$ 道菜肴中吃掉的食物总质量必须恰好为 $m_i$ 克。

请确定品鉴师应从每道菜肴中分别吃掉多少克鱼肉和多少克猪肉，使得最终的多样性达到最小可能值。若存在多种正确方案，输出任意一种即可。

The first line of input data contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each test case's description is preceded by a blank line. Next comes a line that contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of dishes. Then follows $n$ lines, $i$-th of which contains three integers $a_i$, $b_i$ and $m_i$ ($0 \leq a_i, b_i \le 10^6$; $0 \le m_i \le a_i+b_i$) — the mass of fish in $i$-th dish, the mass of meat in $i$-th dish and how many grams in total the taster should eat in $i$-th dish.

The sum of all $n$ values for all input data sets in the test does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的描述前均有一个空行。接下来是一行，包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示菜肴的数量。随后是 $n$ 行，其中第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $m_i$（$0 \leq a_i, b_i \le 10^6$；$0 \le m_i \le a_i+b_i$），分别表示第 $i$ 道菜中鱼的质量、肉的质量，以及品鉴师在第 $i$ 道菜中应食用的总克数。

所有测试数据中各 $n$ 值的总和不超过 $2 \cdot 10^5$。

For each test case, print on the first line the minimum value of variety that can be achieved by eating exactly $m_i$ grams of food (for all $i$ from $1$ to $n$) from a dish $i$.

Then print $n$ lines that describe a way to do this: the $i$-th line should contain two integers $x_i$ and $y_i$ ($0 \leq x_i \leq a_i$; $0 \leq y_i \leq b_i$; $x_i+y_i=m_i$), where $x_i$ is how many grams of fish the taster should eat from $i$-th dish, and $y_i$ is how many grams of meat.

If there are several ways to achieve a minimum balance, print any of them.

对于每个测试用例，在第一行输出：从第 $i$ 道菜（$i$ 从 $1$ 到 $n$）中恰好食用 $m_i$ 克食物所能达到的最小“多样性”值。

然后输出 $n$ 行，描述一种达成该最小值的方法：第 $i$ 行应包含两个整数 $x_i$ 和 $y_i$（满足 $0 \leq x_i \leq a_i$；$0 \leq y_i \leq b_i$；且 $x_i + y_i = m_i$），其中 $x_i$ 表示品鉴者应从第 $i$ 道菜中食用的鱼肉克数，$y_i$ 表示应食用的猪肉克数。

若存在多种方案可达成该最小“多样性”，输出任意一种即可。