CF1607G.Banquet Preparations 1

A known chef has prepared $n$ dishes: the $i$-th dish consists of $a_i$ grams of fish and $b_i$ grams of meat.

The banquet organizers estimate the balance of $n$ dishes as follows. The balance is equal to the absolute value of the difference between the total mass of fish and the total mass of meat.

Technically, the balance equals to $\left|\sum\limits_{i=1}^n a_i - \sum\limits_{i=1}^n b_i\right|$. The smaller the balance, the better.

In order to improve the balance, a taster was invited. He will eat exactly $m$ 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 should eat exactly $m$ grams of each dish in total.

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

一位知名厨师准备了 $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$ 克。

请确定品鉴师应从每道菜肴中各吃多少克鱼肉和牛肉，使得最终的平衡度尽可能小。若存在多种可行方案，任选其一即可。

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

Each test case's description is preceded by a blank line. Next comes a line that contains integers $n$ and $m$ ($1 \leq n \leq 2 \cdot 10^5$; $0 \leq m \leq 10^6$). The next $n$ lines describe dishes, the $i$-th of them contains a pair of integers $a_i$ and $b_i$ ($0 \leq a_i, b_i \le 10^6$) — the masses of fish and meat in the $i$-th dish.

It is guaranteed that it is possible to eat $m$ grams of food from each dish. In other words, $m \leq a_i+b_i$ for all $i$ from $1$ to $n$ inclusive.

The sum of all $n$ values over all test cases in the test does not exceed $2 \cdot 10^5$.

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

每个测试用例的描述前有一空行。接下来是一行，包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$；$0 \leq m \leq 10^6$）。随后的 $n$ 行描述了 $n$ 道菜肴，其中第 $i$ 行包含一对整数 $a_i$ 和 $b_i$（$0 \leq a_i, b_i \le 10^6$），分别表示第 $i$ 道菜肴中鱼肉和牛肉的质量（单位：克）。

题目保证可以从每道菜肴中恰好吃掉 $m$ 克食物。换言之，对所有 $i$（$1 \le i \le n$），均有 $m \leq a_i+b_i$。

所有测试用例中的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print on the first line the minimal balance value that can be achieved by eating exactly $m$ grams of food from each dish.

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$), where $x_i$ is how many grams of fish taster should eat from the $i$-th meal and $y_i$ is how many grams of meat.

If there are several ways to achieve a minimal balance, find any of them.

对于每个测试用例，在第一行输出通过从每道菜中恰好吃 $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$ 表示应吃的肉的克数。

如果存在多种方式可达到最小平衡值，则输出任意一种即可。