Задача D. Армия дроидов ≡

Условие

Торговая Федерация славится своей не очень эффективной военной силой — армией дроидов.

Армия дроидов состоит из N полков, i-й из которых содержит a_i рот по b_i дроидов в каждой. Для повышения огневой мощи и боевой эффективности (если это вообще возможно) руководство Торговой Федерации решило реорганизовать армию.

Основное требование реорганизации — минимизация абсолютной разницы количества дроидов между двумя любыми полками. В ходе реорганизации разрешено изменять количество рот в любом полку и количество дроидов в ротах этого полка, но в рамках одного полка количество дроидов в каждой роте должно быть одинаковым. Общее количество дроидов также должно остаться неизменным.

Генерал Гривус хочет определить минимально возможную абсолютную разницу между полками, а также предложить новый план распределения дроидов.

Абсолютной разницей двух целых чисел называется разница, посчитанная по модулю. Например, |5 − 2| = |3| = 3 или |2 − 5| = |−3| = 3.

Требуется написать программу, которая по текущим данным об армии дроидов определит наилучший вариант реорганизации.

Формат входных данных

Первая строка содержит одно целое число N — количество полков в армии дроидов.

Далее следует N строк, i-я из которых содержит два целых числа a_i и b_i — количество рот в i-м полку и количество дроидов в одной роте этого полка соответственно.

Формат выходных данных

Первая строка должна содержать одно целое число — минимально возможную абсолютную разницу количества дроидов между полками.

Далее должно быть выведено N строк, i-я из которых содержит два целых положительных числа — новое количество рот в i-м полку и новое количество дроидов в одной роте этого полка соответственно.

Если ответов несколько, разрешается вывести любой из них.

Ограничения

2 ≤ N ≤ 10⁵

1 ≤ a_i, b_i ≤ 10³

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснения к примерам

В первом примере, после реорганизации, количество дроидов в первом полку составит 16, а во втором полку — 15.

Примеры тестов

2
3 7
2 5

1
4 4
3 5

3
6 5
4 6
3 18

0
6 6
4 9
3 12