Прямоугольное поле высоты $$$2^N$$$ и ширины $$$2^N-1$$$ разбито на квадратные единичные клеточки. Сначала выделяется прямоугольная область высоты $$$2^N$$$ и ширины $$$2^{N-1}$$$, прилегающая к левому краю поля. Затем для каждой прямоугольной области справа приклеиваются две области вдвое меньшего размера. Процесс продолжается до тех пор, пока размеры областей не станут $$$2 \times 1$$$, и всё поле не будет заполнено.
Далее, клеточки поля красятся в чёрный и жёлтый цвет по следующему принципу. Самая большая область красится в чёрный цвет. Затем для каждой области нижняя из прилегающих слева областей красится в тот же цвет, что и текущая область, а верхняя — в противоположный.
Результат раскраски для $$$N=4$$$ иллюстрирует следующая картинка:
У Вас есть $$$q$$$ запросов, каждый из которых задаёт произвольный прямоугольник внутри поля. Посчитайте для каждого запроса количество чёрных клеток, которые покрывает соответствующий прямоугольник.
В первой строке дано два целых числа $$$N$$$ и $$$q$$$ ($$$1 \le N \le 30$$$, $$$1 \le q \le 10^4$$$).
Далее идут $$$q$$$ строк, в $$$i$$$-й из них дано описание $$$i$$$-го запроса: четыре целых числа $$$r_i$$$, $$$c_i$$$, $$$h_i$$$, $$$w_i$$$, где $$$r_i$$$, и $$$c_i$$$ — номер строки и номер столбца клеточки, в которой находится левый верхний угол прямоугольника, а $$$h_i$$$ и $$$w_i$$$ — высота и ширина прямоугольника соответственно ($$$1 \le r_i, h_i, r_i+h_i-1 \le 2^N$$$, $$$1 \le c_i, w_i, c_i+w_i-1 \le 2^N-1$$$, $$$1 \le i \le q$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из них должно быть одно целое число — ответ на $$$i$$$-й запрос.
Отметим, что ответы могут получиться очень большими и не поместиться в 32-битную переменную. Пожалуйста используйте 64-битный тип данных.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | — | — | Тесты из условия |
| 1 | 30 | $$$N \le 5, q \le 1000$$$ | 0 | |
| 2 | 20 | $$$N \le 10, q \le 10^4$$$ | 0, 1 | |
| 3 | 20 | $$$N \le 15, q \le 100$$$ | 0, 1 | |
| 4 | 20 | $$$N \le 20, q \le 10^4$$$ | 0-3 | |
| 5 | 10 | $$$N \le 30, q \le 10^4$$$ | 0-4 | Полные ограничения |
3 41 1 8 72 4 6 44 1 2 66 3 1 3
44 14 10 3
Прямоугольники из примера, для которых нужно посчитать количество чёрных клеточек, показаны на следующем рисунке:
