Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

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

Сумма всех значений $$$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$$$ — сколько грамм мяса.

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

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