Макс и расстояния
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
distances.in
вывод
distances.out

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

Макс решил поиграть с ними: он сгенерировал матрицу расстояний d, каждый элемент которой равен di, j = |xai - xbj|, то есть di, j элемент равен расстоянию между ai и bj точкой.

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

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

Входные данные

В первой строке находится натуральное число n (1 ≤ n ≤ 1000). В следующих n строках находится матрица d (0 ≤ di, j ≤ 109). Все числа в матрице — целые числа.

Выходные данные

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

во второй строке — неубыващий массив целых чисел x (|xi| ≤ 109; xi ≤ xi + 1),

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

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

Если таких x, a и b не существует — выведите «NO».

Примеры

Входные данные
4
3 2 1 0
2 1 0 1
1 0 1 2
0 1 2 3
Выходные данные
YES
0 1 2 3
1 2 3 4
4 3 2 1
Входные данные
3
1 0 2
1 1 1
1 1 0
Выходные данные
NO
Входные данные
4
7 0 2 1
9 2 0 3
0 7 9 6
6 1 3 0
Выходные данные
YES
0 2 3 9
2 1 4 3
4 2 1 3

Примечание

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