Подсчет коров
Подсчет коров
Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).
Размещение коров весьма занимательно. Для каждой ячейки (x, y) с x ≥ 0 и y ≥ 0, существует корова в ячейке (x, y) если для всех целых чисел k ≥ 0, остатки ⌊x / 3k
⌋ и ⌊y / 3k
⌋ по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для 0 ≤ x, y < 9, которые содержат коров обозначены цифрой 1 на рисунке ниже.
x
012345678
0 101000101
1 010000010
2 101000101
3 000101000
y 4 000010000
5 000101000
6 101000101
7 010000010
8 101000101
ФД интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт q вопросов, кажый содержит три целых числа xi
, yi
, di
. Для каждого вопроса ФД хочет знать, сколько коров в ячейках (xi
, yi
) до (xi
+ di
, yi
+ di
) (включая конечные точки).
Входные данные
Первая строка содержит q (1 ≤ q ≤ 104
) - количество вопросов.
Каждая из следующих q строк содержит 3 целых числа di
, xi
и yi
(0 ≤ xi
, yi
, di
≤ 1018
).
Выходные данные
Выведите q строк, по одной для каждого вопроса - одно целое число - ответ.
8 10 0 0 10 0 1 9 0 2 8 0 2 0 1 7 1 1 7 2 1 7 1000000000000000000 1000000000000000000 1000000000000000000
11 0 4 3 1 2 2 1000000000000000001