一位知名厨师准备了 $$$n$$$ 菜肴:第 $$$i$$$ 菜肴由 $$$a_i$$$ 克鱼和 $$$b_i$$$ 克肉组成。
宴会组织者估算 $$$n$$$ 菜品的余额如下。平衡等于鱼的总质量与肉的总质量之差的绝对值。
从技术上讲,余额等于 $$$\left|\sum\limits_{i=1}^n a_i - \sum\limits_{i=1}^n b_i\right|$$$。余额越小越好。
为了提高平衡性,请了品尝师。他会吃掉每道菜中的 $$$m$$$ 克食物。对于每道菜,品尝者分别决定他要吃多少鱼和多少肉。唯一的条件是他必须吃掉每道菜总共 $$$m$$$ 克。
确定品尝者应该从每道菜中吃多少类型的食物,以使平衡值尽可能最小。如果有多个正确答案,您可以选择其中一个。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的描述前面都有一个空行。接下来是包含整数 $$$n$$$ 和 $$$m$$$ 的行($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$0 \leq m \leq 10^6$$$)。接下来的 $$$n$$$ 行描述菜肴,其中第 $$$i$$$ 包含一对整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \leq a_i, b_i \le 10^6$$$) — 第 $$$i$$$ 菜肴中的鱼和肉的质量。
保证每道菜可以吃$$$m$$$克食物。换句话说,$$$m \leq a_i+b_i$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 包括在内。
测试中所有测试用例的所有 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在第一行打印通过吃每道菜中 $$$m$$$ 克食物可以达到的最小平衡值。
然后打印 $$$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$$$),其中 $$$x_i$$$ 是品尝者应从第 $$$i$$$ 餐中吃多少克鱼,$$$y_i$$$ 是多少克肉。
如果有多种方法可以实现最小平衡,请找到其中任何一种。
示例
输入 #1
8 1 5 3 4 1 6 3 4 2 2 1 3 4 2 2 4 1 3 1 7 3 6 1 7 1 8 1 9 3 6 1 8 1 9 30 10 3 4 3 1 3 2 4 1 5 4 0 7 6 4 0 8 4 1 5 3
输出 #1
0 2 3 1 3 3 0 1 1 1 1 2 1 3 0 4 3 0 6 0 6 0 6 7 1 5 1 5 6 0 0 3 1 3 1 3 1 0 0 4 2 2 0 4 3 1 1 3