Шырдак Серпинского


Отправить решение Решать в редакторе

Сложность: 75%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Мастерица из Кочкора Айгерим задумала шырдак с узором «ковёр Серпинского». Узор порядка k — это квадрат из 3^k × 3^k клеток, каждая клетка либо прошита цветным войлоком, либо пустая:

  • узор порядка 0 — одна прошитая клетка;
  • узор порядка k делится на 3 × 3 одинаковых квадрата со стороной 3^(k−1); центральный квадрат пустой, а каждый из восьми остальных — узор порядка k − 1.

Рисунок

Строки и столбцы узора пронумерованы от 0 до 3^k − 1, строки сверху вниз, столбцы слева направо. Заказчики то и дело спрашивают, сколько войлока уйдёт на прямоугольный кусок шырдака. Для каждого запроса x1 y1 x2 y2 найдите количество прошитых клеток в прямоугольнике из строк с x1 по x2 и столбцов с y1 по y2 (включительно).

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

В первой строке — два целых числа k и q (0 ≤ k ≤ 20, 1 ≤ q ≤ 10⁵). В каждой из следующих q строк — четыре целых числа x1 y1 x2 y2 (0 ≤ x1 ≤ x2 < 3^k, 0 ≤ y1 ≤ y2 < 3^k).

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

Для каждого запроса выведите в отдельной строке количество прошитых клеток.

Пример 1

Вход:

2 4
0 0 8 8
3 3 5 5
1 0 4 2
4 4 4 4

Выход:

64
0
10
0

Пояснение

На рисунке — узор порядка 2 из примера. В первом запросе спрашивают про весь узор: в нём 8² = 64 прошитые клетки.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов k ≤ 5, ещё в 30 % тестов q ≤ 1000.

Примечание

Ответ может достигать 8²⁰ ≈ 1,15 · 10¹⁸ — используйте 64-битные целые числа.


Комментарии

Еще нет ни одного комментария.