H. Подготовка банкета 2
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известный шеф-повар опять приготовил $$$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 \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$$$-м блюде, количество грамм мяса в $$$i$$$-м блюде и сколько суммарно грамм дегустатор должен съесть в $$$i$$$-м блюде.

Сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в первой строке минимальное значение разнообразия, которое можно достичь, съев из блюда $$$i$$$ ровно $$$m_i$$$ грамм еды (для всех $$$i$$$ от $$$1$$$ до $$$n$$$).

Далее выведите $$$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$$$ — сколько грамм мяса.

Если есть несколько способов добиться минимального баланса, выведите любой из них.

Пример
Входные данные
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
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