Игорь много занимался шахматами, и теперь ему надоела игра по обычным правилам. Он собирается придумать новые правила игры и обрести мировую славу.

Доска в шахматах Игоря имеет форму квадрата n × n клеток. Игорь решил, что простота правил — залог успеха, поэтому в его игре будет всего один тип фигур, кроме того, все фигуры в его игре одного цвета. Всевозможные ходы фигуры описываются множеством векторов смещений. В следующем абзаце находится формальное описание допустимых ходов.

Пусть горизонтали доски пронумерованы сверху вниз, а вертикали — слева направо от 1 до n. Сопоставим каждой клетке пару чисел (x, y) — номер соответствующей вертикали и горизонтали. Каждый из возможных ходов фигуры задается парой чисел (dx, dy), используя этот ход, фигура с поля (x, y) перемещается на поле (x + dx, y + dy). Ход можно совершить, если поле (x + dx, y + dy) находится внутри границ доски, и на нем нет другой фигуры. Фигуры, стоящие на полях, отличных от (x, y) и (x + dx, y + dy), не влияют на возможность совершения данного хода (например, как при ходе коня в обычных шахматах).

Игорь предлагает вам угадать, какие ходы может делать его фигура. Он расставил на доске несколько фигур и про каждое незанятое поле сообщил вам, находится ли оно под боем хотя бы одной фигуры (т.е. может ли какая-либо из стоящих на поле фигур сходить в это поле). Восстановите возможный набор ходов фигуры, либо определите, что Игорь ошибся и такая ситуация невозможна ни при каком наборе ходов.