← 返回题目列表

Codeforces · 1607/H

H. 宴会准备2

中文机器翻译题面 查看原题

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

如果同时 $$a_i=a_j$$$ 和 $$$b_i=b_j$$$ 存在,则宴会组织者认为两道菜 $$$i$$$ 和 $$$j$$$ 相等。

宴会组织者估计$$$n$$$菜肴​​的种类如下。一套菜肴的品种等于其中不同菜肴的数量。品种越少越好。

为了减少品种,请了品尝师。他会吃掉每道菜中的 $$$m_i$$$ 克食物。对于每道菜,品尝者分别决定他要吃多少鱼和多少肉。唯一的条件是他总共要吃掉第 $$$i$$$ 道菜的 $$$m_i$$$ 克。

确定品尝者应该从每道菜中吃多少类型的食物,以使品种价值尽可能最小。如果有多个正确答案,则可以输出其中任何一个。

输入

输入数据的第一行包含一个整数 $$$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$$$-th 道菜、第 $$$i$$$-th 道菜中的肉质量以及品尝者在第 $$$i$$$-th 道菜中总共应吃多少克。

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

输出

对于每个测试用例,在第一行打印通过从 $$$i$$$ 菜肴中吃掉 $$$m_i$$$ 克食物(从 $$$1$$$ 到 $$$n$$$ 的所有 $$$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$$$ 是多少克肉。

如果有多种方法可以达到最低余额,请打印其中任何一种。

示例

输入 #1

5

3
10 10 2
9 9 0
10 9 1

2
3 4 1
5 1 2

3
7 2 5
6 5 4
5 5 6

1
13 42 50

5
5 7 12
3 1 4
7 3 7
0 0 0
4 1 5

输出 #1

1
1 1
0 0
1 0
2
0 1
1 1
2
3 2
0 4
1 5
1
8 42
2
5 7
3 1
4 3
0 0
4 1