| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 8 | 5 | 5 | 62.500% |
Макс нашел массив $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>>.
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
Обратите внимание, что входные данные могут иметь достаточно большой объем, поэтому рекомендуется использовать быстрые потоки ввода-вывода вашего языка.