Banquet Preparations 2
Contest: Codeforces Round 753 (Div. 3)
Difficulty rating: 2200
Tags: greedy, sortings, two pointers

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
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

Editorial:
Note that dishes can become equal if and only if they have equal values of $$$a_i + b_i - m_i$$$, that is, how much fish and meat remain in them in total after "tasting". Let's calculate this value for each dish and group all the dishes with equal calculated values.
The minimum amount of fish that can remain in the $$$i$$$-th dish is $$$a_i^\mathtt{min} = \max(0, a_i - m_i)$$$ in case where the maximum possible mass of fish is eaten. Similarly, the maximum amount of fish that can remain is $$$a_i^\mathtt{max} = a_i + \min(0, b_i - m_i)$$$ in case where the maximum possible mass of meat is eaten.
Consider one of the groups $$$g$$$ in which there are all the dishes with equal values $$$G = a_i + b_i - m_i$$$. We sill assign each dish a corresponding segment on the coordinate line between $$$a_i^{\mathtt{min}}$$$ and $$$a_i^{\mathtt{max}}$$$. This segment specifies all possible values of the remaining mass of fish in the dish; any value on it is achievable by replacing eating some mass of fish with the same mass of meat. And since $$$G$$$ is common, the same amount of remaining fish will imply the same amount of remaining meat, thus, equality.
Let us solve the problem for each group independently. Within a group, the problem is reduced to choosing as few points as possible that "cover" all the segments described in the last paragraph (that is, that there should be a point inside each segment). Each selected point will correspond to the resulting dish, and it being inside a segment will mean that such a resulting dish can be obtained from the corresponding starting one. Such a problem is solved as follows:
1. we choose a segment with the minimal right end; because it must contain at least one chosen point we'll greedily choose it equal to its right end;
2. there's no point in choosing a point to the left from it, since it will not cover more segments than the right end of the segment in question;
3. we'll mark all segments containing this point as covered, and repeat the algorithm for the next unprocessed segment with the minimal right end.
For this algorithm, it is sufficient to sort the segments by their right ends within each group and iterate through the segments, greedily selecting points in the manner described above. The set of points obtained at the end will be the answer, and its size and the information about the point selected within each segment should be printed in the output. If for a dish $$$(a_i, b_i, m_i)$$$ a point $$$x$$$ is chosen inside its corresponding segment, then there should be exactly $$$x$$$ of fish left in it, that is, you should output the numbers $$$a_i - x$$$ and $$$m_i - (a_i - x)$$$ in the answer.