Кривая Гильберта в Ботаническом саду
В Ботаническом саду Бишкека разбили квадратную опытную делянку 2^k × 2^k клеток. Садовник поливает клетки по кривой Гильберта — пути, который обходит все клетки, каждый раз переходя в соседнюю по стороне.
Клетка задаётся координатами (x, y), 0 ≤ x, y < 2^k; ось x направлена вправо, ось y — вверх. Кривая порядка 0 — одна клетка. Кривая порядка k составлена из четырёх кривых порядка k − 1, по одной в каждой четверти квадрата, которые проходятся в таком порядке:
- левая нижняя четверть — кривая порядка
k − 1, отражённая относительно диагоналиy = x; - левая верхняя четверть — кривая порядка
k − 1без изменений; - правая верхняя четверть — кривая порядка
k − 1без изменений; - правая нижняя четверть — кривая порядка
k − 1, отражённая относительно другой диагонали четверти (идущей из её левого верхнего угла в правый нижний).
Так кривая порядка 1 обходит клетки (0, 0) → (0, 1) → (1, 1) → (1, 0). Клетки нумеруются в порядке обхода числами от 0 до 4^k − 1.
Каждый вечер садовник получает заказ на прямоугольный участок x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. Ему нужно знать, на каком шаге он впервые попадёт на этот участок и на каком шаге покинет его в последний раз. Для каждого участка выведите наименьший и наибольший номер клетки участка.
Входные данные
В первой строке — два целых числа k и q (0 ≤ k ≤ 30, 1 ≤ q ≤ 10⁵). В каждой из следующих q строк — четыре целых числа x1 y1 x2 y2 (0 ≤ x1 ≤ x2 < 2^k, 0 ≤ y1 ≤ y2 < 2^k).
Выходные данные
Для каждого запроса выведите два числа: наименьший и наибольший номер клетки в прямоугольнике.
Пример 1
Вход:
2 4
0 0 3 3
1 2 1 2
2 0 3 1
0 1 3 2
Выход:
0 15
7 7
12 15
2 13
Пояснение
На рисунке — кривые порядков 1, 2 и 3. В кривой порядка 2 клетка (0, 0) имеет номер 0, клетка (3, 0) — номер 15, клетка (1, 2) — номер 7.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов k ≤ 6, ещё в 20 % тестов q ≤ 1000.
Комментарии