Шырдак Серпинского
Мастерица из Кочкора Айгерим задумала шырдак с узором «ковёр Серпинского». Узор порядка 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-битные целые числа.
Комментарии