Кратчайшая последовательность поворотов

C++17, C++20, Python 3, Go, Kotlindaily-space-004-minimum-rotations

Дана непустая модель из единичных кубиков и три целевых силуэта размером 3×3. За один ход разрешён один из четырёх поворотов, применяемый ко всем координатам:

$X^+: (x,y,z) \mapsto (x,-z,y)$ ;
$X^-: (x,y,z) \mapsto (x,z,-y)$ ;
$Y^+: (x,y,z) \mapsto (z,y,-x)$ ;
$Y^-: (x,y,z) \mapsto (-z,y,x)$ .

Это повороты на 90° вокруг неподвижных осей. Поворот вокруг $Z$ отдельным ходом не разрешён. Координаты после хода могут стать отрицательными.

Для модели строят три множества пар: спереди $(x,y)$ , сверху $(x,z)$ , справа $(-z,y)$ . Каждую проекцию отдельно сдвигают так, чтобы минимум первой и минимум второй координаты стали нулевыми. Затем пару $(u,v)$ отмечают единицей в строке $v$ , столбце $u$ матрицы 3×3; остальные клетки — нули. Нумерация строк и столбцов начинается с нуля, строки перечисляются сверху вниз.

Найдите минимальное число ходов, после которых все три полученные матрицы в точности совпадут с целевыми. Если это невозможно, выведите -1. Целевые матрицы дополнительно сдвигать, отражать или поворачивать нельзя.

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

Первая строка содержит $N$ ( $1 \le N \le 27$ ). Следующие $N$ строк содержат различные целые тройки $x_i,y_i,z_i$ ( $0 \le x_i,y_i,z_i \le 2$ ). Связность модели не гарантируется. Далее идут 9 строк из 3 символов 0 или 1: сначала 3 строки вида спереди, затем 3 строки вида сверху, затем 3 строки вида справа. Между матрицами нет служебных строк.

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

Выведите минимальное число разрешённых поворотов или -1.

Примеры

Пример 1

Input

Output

Исходное положение уже подходит.

Пример 2

Input

Output

Достаточно одного поворота X+.

Пример 3

Input

Output

-1

Непустая модель не даёт пустые проекции.

Примечания

Оси сцены: x вправо, y вниз, z к зрителю. Определяющими являются формулы в условии. Для сравнения достаточно силуэтов: разные трёхмерные модели могут иметь одинаковые проекции.