Известно, что господин Чичиков зарабатывал свой капитал и таким способом: он спорил со всякими недотёпами, что сможет доказать, что квадратную доску размера 512 × 512 нельзя замостить следующими фигурами:
X XX X XX
XX X XX X
и всегда выигрывал. Однако один из недотёп оказался не так уж глуп, и сказал, что сможет замостить такими фигурами доску размера 512 × 512 без правой верхней клетки. Чичиков, не подумав, ляпнул, что он вообще может любую доску размера 2n × 2n без одной произвольной клетки замостить такими фигурами. Слово за слово, они поспорили. Чичиков чувствует, что сам он не докажет свою правоту. Помогите же ему!
Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
В первой строке записано целое число n (1 ≤ n ≤ 9). Во второй строке через пробел даны два целых числа x, y: координаты «выколотой» клетки доски (1 ≤ x, y ≤ 2n), x — номер строки, y — номер столбца. Левый верхний угол доски имеет координаты (1, 1).
Ваша программа должна выдать 2n строчек по 2n чисел в каждой строке. На месте выбитой клетки должно стоять число 0. На месте остальных клеток должны стоять числа от 1 до (22n − 1) / 3 — номер фигуры, закрывающей данную клетку. Разумеется, одинаковые номера должны образовывать фигуры. Если же такую доску нельзя покрыть фигурами, выведите «−1».
| Исходные данные | Результат |
|---|---|
| 2 1 1 |
0 1 3 3 1 1 4 3 2 4 4 5 2 2 5 5 |