| Codeforces Round 372 (Div. 1) |
|---|
| Закончено |
Кодер ZS обожает лабиринты. Ваша задача — построить такой, чтобы он мог с ним играть. Лабиринт состоит из n × m комнат, которые расположены в n строк (пронумерованных сверху вниз начиная с 1) и m столбцов (пронумерованных слева направо начиная с 1). Комната в i-й строке и j-м столбце обозначается (i, j). Игрок начинает в комнате (1, 1) и хочет попасть в комнату (n, m).
Каждая комната содержит четыре двери (за исключением комнат на границе лабиринта), по одной на каждой из ее стен, так что две соседние по стене комнаты делят одну и ту же дверь. Некоторые из дверей заперты, и проходить через них запрещено. К примеру, если дверь между (i, j) и (i, j + 1) заперта, то пройти из (i, j) в (i, j + 1) нельзя. Также между комнатами можно перемещаться только вниз (из комнаты (i, j) в комнату (i + 1, j)) или вправо (из комнаты (i, j) в комнату (i, j + 1)), если соответствующая дверь не заперта.
Рисунок изображает лабиринт с запертыми дверями. Разноцветные стрелки изображают всевозможные пути, а красный крест означает запертую дверь. Кодер ZS считает, что сложность лабиринта равна x, если существует ровно x способов пройти из комнаты (1, 1) в комнату (n, m). Два способа считаются различными если они различаются в последовательности посещенных в пути комнат.
Ваша задача — создать лабиринт, сложность которого в точности равна T. В дополнение, Кодер ZS не любит большие лабиринты, так что его размер и количество запертых дверей ограничены. Звучит достаточно просто, не правда ли?
Первая и единственная строка входных данных содержит единственное целое число T (1 ≤ T ≤ 1018), сложность требуемого лабиринта.
Первая строка должна содержать два целых числа n и m (1 ≤ n, m ≤ 50) — количество строк и столбцов в лабиринте соответственно.
Следующая строка должна содержать целое число k (0 ≤ k ≤ 300) — количество запертых дверей в лабиринте.
Следующие k строк должны описывать запертые двери. Каждая из них должна содержать четыре целых числа x1, y1, x2, y2, означающих, что дверь между комнатами (x1, y1) и (x2, y2) заперта. Заметьте, что комната (x2, y2) должна быть соседней с комнатой (x1, y1), т.е. x2 + y2 должно равняться x1 + y1 + 1. Никакая дверь не должна присутствовать в списке дважды.
Гарантируется, что хотя бы одно решение существует. Если существует несколько решений, выведите любое из них.
3
3 2
0
4
4 3
3
1 2 2 2
3 2 3 3
1 3 2 3
Вот так выглядят входные и выходные данные к примерам из условия. Разноцветные стрелки изображают всевозможные пути, а красный крест означает запертую дверь.
В первом примере из условия:
Во втором примере из условия:
