Дана табличка n × n, в клетках которой записаны натуральные числа от 1 до 109.
Существует ли путь из клетки (1, 1) в клетку (n, n) такой, что НОД чисел на этом пути больше 1? Перемещаться можно по клеткам только вправо и только вниз. Например, из клетки с координатами (x, y) можно перейти в клетку (x, y + 1) или в клетку (x + 1, y).
Формат ввода
В первой строке вводится n — сторона таблички.
В следующих n строках вводится по n чисел — сама таблица.
Формат вывода
Если путь существует, то выведите 0 при перемещении вправо и 1 при перемещении вниз. Если удовлетворяющих условию путей несколько, то выведите любой подходящий путь.
Если пути не существует, выведите -1.
НА ЛЮБОМ ЯЗЫКЕ
