Підрахунок корів#11215

Підрахунок корів

1 секунда

128 мегабайтів

Дуже складна

Корови фермера Джона розселилися на його найбільшому пасовищі, яке можна уявити як велику двовимірну решітку квадратних клітин (уявіть собі гігантську шахову дошку).

Розташування корів на пасовищі досить цікаве. Для кожної клітини $(x, y)$ , де $x \geq 0$ x \ge 0 і $y \geq 0$ y \ge 0, у клітині $(x, y)$ є корова, якщо для всіх цілих $k \geq 0$ k \ge 0 залишки від ділення $⌊ \frac{x}{3 ^{k}} ⌋$ \left\lfloor \frac{x}{3^k} \right\rfloor і $⌊ \frac{y}{3 ^{k}} ⌋$ \left\lfloor \frac{y}{3^k} \right\rfloor на $3$ мають однакову парність. Іншими словами, обидва залишки непарні (дорівнюють $1$ ), або обидва парні (дорівнюють $0$ або $2$ ). Наприклад, клітини серед $0 \leq x, y < 9$ 0 \le x, y < 9, у яких є корови, позначені одиницями на рисунку нижче:

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Фермер Джон цікавиться, скільки корів знаходиться у певних діагональних областях його пасовища. Він ставить $q$ запитів, кожен з яких складається з трьох цілих чисел $x_{i}$ x_i, $y_{i}$ y_i, $d_{i}$ d_i. Для кожного запиту фермер Джон хоче дізнатися, скільки корів знаходиться у клітинах на діагоналі від $(x_{i}, y_{i})$ (x_i, y_i) до $(x_{i} + d_{i}, y_{i} + d_{i})$ (x_i + d_i, y_i + d_i) включно.

Вхідні дані

Перший рядок містить ціле число $q$ ( $1 \leq q \leq 1 0^{4}$ 1 \le q \le 10^4) — кількість запитів.

Кожен з наступних $q$ рядків містить три цілих числа $d_{i}$ d_i, $x_{i}$ x_i, $y_{i}$ y_i ( $0 \leq x_{i}, y_{i}, d_{i} \leq 1 0^{18}$ 0 \le x_i, y_i, d_i \le 10^{18}) — опис запиту.

Вихідні дані

Виведіть $q$ рядків, по одному числу у кожному — відповідь на відповідний запит.

Приклади

Приклад 1