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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105

1 ≤ ai, bi ≤ 103

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N
1 66 2 ≤ N ≤ 102
2 34 2 ≤ N ≤ 105 1

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

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

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

Стандартный вход Стандартный выход
1
2
3 7
2 5
1
4 4
3 5
2
3
6 5
4 6
3 18
0
6 6
4 9
3 12

0.081s 0.009s 13