• Ломаная
  BROKEN

Маленький мальчик взял листок бумаги в клетку размером NxN клеток и нарисовал на нем замкнутую M-звенную ломаную с вершинами в узлах клеток. После этого он выписал квадраты длин звеньев ломаной в порядке их обхода по ломаной, а затем выкинул свой рисунок. Необходимо определить, существует ли хотя бы одна ломаная, соответствующая записанным мальчиком данным, или он ошибся в подсчете расстояний. Если такая ломаная существует, то нужно ее воспроизвести.

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

Технические требования:

Входной файл: INPUT.TXT  
Выходной файл: OUTPUT.TXT  
Ограничение по времени тестирования: 5 секунд на один тест

Формат входных данных: входной файл INPUT.TXT состоит из двух строк. В первой строке содержатся два целых числа: 

N – размер бумаги в клетку (1<=N<=15);
M – количество звеньев в ломаной (3<=M<=20);
Вторая строка содержит последовательность из M целых чисел, являющихся квадратами длин звеньев ломаной.

Формат выходных данных: в случае наличия решения данной задачи выходной файл OUTPUT.TXT должен состоять из M строк, в i-ой строке которого содержатся координаты вершин ломаной X_i и Y_i, где X_i, Y_i – целые числа и 0<=X_i<=N, 0<=Y_i<=N. Порядок записи координат вершин ломаной в строках должен соответствовать порядку записи квадратов длин звеньев ломаной во входном файле.

В случае наличия нескольких решений следует найти хотя бы одно из них. Если по исходным данным ломаную восстановить невозможно, то выходной файл должен содержать сообщение "NO".