CF1607H Banquet Preparations 2

厨师又做了 $n$ 道菜：第 $i$ 道菜包含 $a_i$ 克鱼肉和 $b_i$ 克肉类。 宴会组织者认为，如果两道菜 $i$ 和 $j$ 满足 $a_i=a_j$ 且 $b_i=b_j$，则这两道菜是相同的。 宴会组织者用如下方式评估 $n$ 道菜的多样性。一组菜肴的多样性等于其中不同菜肴的数量。多样性越低越好。 为了降低多样性，邀请了一位品尝者。他会从每道菜中恰好吃掉 $m_i$ 克食物。对于每道菜，品尝者可以分别决定吃多少克鱼肉和多少克肉类。唯一的条件是，他从第 $i$ 道菜中总共吃掉恰好 $m_i$ 克。 请你确定品尝者应该从每道菜中吃掉多少克鱼肉和多少克肉类，使得多样性的值尽可能小。如果有多种方案，输出任意一种即可。

输入的第一行为一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例前有一个空行。接下来一行包含一个整数 $n$（$1 \leq n \leq 2 \times 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 \times 10^5$。

对于每个测试用例，第一行输出通过从每道菜中吃掉恰好 $m_i$ 克食物后能够达到的最小多样性值。 接下来输出 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$0 \leq x_i \leq a_i$；$0 \leq y_i \leq b_i$；$x_i + y_i = m_i$），表示品尝者从第 $i$ 道菜中应吃掉的鱼肉和肉类的克数。 如果有多种达到最小多样性的方案，输出任意一种即可。

由 ChatGPT 4.1 翻译