29226번 - Магические стержни 다국어

У Беллы есть $n$ пронумерованных магических стержней. Для получения магической энергии Белла поджигает каждый стержень с двух концов (возможно, в различные моменты времени). Огонь распространяется со скоростью один сантиметр в секунду. В момент времени, когда огонь охватывает стержень целиком, его магическая энергия освобождается.

Вам известно что длина $i$-го стержня равна $l_i$ сантиметрам. Помогите Белле выбрать моменты времени поджога концов каждого стержня так, чтобы магическая энергия со всех стержней освободилась в один и тот же момент времени. При этом Белла хочет, чтобы в $i$-м стержне последняя точка, которая будет охвачена огнем, находилась на расстоянии $d_i$ от первого конца стержня.

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

В первой строке задано одно целое число $n$ ($1 \le n \le 10,000$) --- количество стержней у Беллы. В следующих $n$ строках записано по два числа $l_i$ и $d_i$ ($2 \le l_i \le 1,000,000$, $0 < d_i < l_i$) --- длина $i$-го стержня, а также расстояние от первого конца $i$-го стержня до точки на этом стержне, которая должна загореться последней.

В $i$-й строчке выходного файла выведите два положительных целых числа $t_{i1}$, $t_{i2}$ --- моменты времени, в которые надо поджечь первый и второй концы $i$-го стержня соответственно.