Крупный предприниматель Владимир Дубинин, в недалёком прошлом больше известный как Вован Палёный, контролирует трест из N предприятий. Бывший подельник Владимира, а ныне известный банкир Александр Кулаков по прозвищу Саня Кривой владеет холдингом из N банков. Как и полагается у старых друзей, предприятия г-н Дубинина берут кредиты исключительно у банков г-н Кулакова, в том время как банки г-на Кулакова выдают кредиты только предприятиям г-на Дубинина. Причём с целью уклонения от уплаты налогов вся информация о размерах кредитов до недавнего времени тщательно скрывалась.

Но в один прекрасный день на пути совместного бизнеса встал давний конкурент Владимира и Александра генерал милиции Иван Ломов, когда-то носивший кличку Ваня Гнилой. Г-н Ломов мечтал заставить г-на Дубинина и г-на Кулакова заплатить за старые обиды. В ходе блестящей операции (более подробно эта история описана в задаче "Кредитные операции") он стал обладателем так называемой кредитной матрицы, т.е. квадратной таблицы из N строк и N столбцов, в которой каждый элемент A[i, j] равен размеру кредита в долларах, взятого i-м предприятием г-на Дубинина у j-го банка г-на Кулакова.

Выражение "заплатить за старые обиды" Иван понимал буквально, и поэтому не стал терять времени и передал кредитную матрицу (разумеется, за достойное вознаграждение) своему старинному приятелю начальнику налоговой полиции Петру Быкову, некогда фигурировавшему в криминальных хрониках исключительно как Петя Бык. На основании столь прочной доказательной базы г-н Быков мог отправить Владимира и Александра топтать зону до второго пришествия, но... Годы службы в налоговой полиции не прошли даром, и Пётр сразу смекнул, что на этом деле можно изрядно нажиться. Особенно если применить системный подход.

Системный подход в понимании г-на Быкова сводился к тому, что каждое предприятие г-на Дубинина должно заплатить в качестве взятки BR[i] долларов, а каждый банк г-на Кулакова - BC[j] долларов. Размер каждого кредита не должен превышать сумму взятки предприятия, взявшего этот кредит, и взятки банка, его выдавшего (т.е. должно выполняться условие A[i, j] ≤ BR[i]+BC[j]). При этом размеры взяток должны выражаться неотрицательными целыми числами, поскольку Пётр бросил школу во втором классе и о существовании каких-то других чисел даже не догадывается. Что, впрочем, не мешает ему занимать высокую должность начальника налоговой полиции, т.к. большинство его подчинённых вообще никогда не ходили в школу.

К чести г-на Быкова, он проявил определённое благородство и предоставил Владимиру и Александру право самостоятельно определить размеры взяток, удовлетворяющих этим условиям. На общем совете директоров, традиционно проходившем в бане, г-н Дубинин и г-н Кулаков вполне разумно постановили, что суммарный размер всех взяток должен быть минимально возможным и привлекли к решению этой задачи своего лучшего программиста Александра Сергеева.

Первая строка содержит целое число N (2 ≤ N ≤ 100). Каждая из следующих N строк содержит N целых чисел - соответствующие элементы A[i, j] (0 ≤ A[i, j] ≤ 10⁶) кредитной матрицы.

В первую строку вывести через пробел оптимальные значения BR[i] для всех предприятий. Во вторую строку вывести через пробел оптимальные значения BC[j] для всех банков. Если задача имеет несколько решений, то вывести любое из них.