28928번 - Макс и расстояния 스페셜 저지다국어

Макс нашел массив $x$ из $n$ целочисленных точек на прямой, упорядоченный по неубыванию. Также у Макса есть две перестановки чисел $a$ и $b$ от $1$ до $n$, которые ему подарили на день рождения.

Макс решил поиграть с ними: он сгенерировал матрицу расстояний $d$, каждый элемент которой равен $d_{i,j} = |x_{a_i} - x_{b_j}|$, то есть $d_{i,j}$ элемент равен расстоянию между $a_i$ и $b_j$ точкой.

Макс еще не успел наиграться с массивами, как после очередной уборки Кэти они куда-то потерялись. Все до одного: и $x$, и $a$, и $b$. Макс решил пойти на экстренные меры: у него сохранилась матрица расстояний $d$, и он хочет восстановить какой-то неубывающий массив $x$, а также две перестановки $a$ и $b$, с помощью которых можно сгенерировать матрицу расстояний, равную $d$. Однако, могло случиться так, что Макс ошибся при подсчете $d$, и восстановить $x$, $a$ и $b$ не получится.

Помогите Максу восстановить их.

В первой строке находится натуральное число $n$ ($1 \le n \le 1000$). В следующих $n$ строках находится матрица $d$ ($0 \le d_{i,j} \le 10^9$). Все числа в матрице --- целые числа.

В первой строке выведите <<YES>>, если существуют такие $x$, $a$ и $b$, с помощью которых можно сгенерировать матрицу, равную $d$,

во второй строке --- неубыващий массив целых чисел $x$ $(|x_i| \le 10^9$; $x_i \le x_{i+1}$),

в третьей строке --- перестановку чисел $a$ от $1$ до $n$,

в четвертой строке --- перестановку чисел $b$ от $1$ до $n$.

Если таких $x$, $a$ и $b$ не существует --- выведите <<NO>>.

Обратите внимание, что входные данные могут иметь достаточно большой объем, поэтому рекомендуется использовать быстрые потоки ввода-вывода вашего языка.