İnəklərin sayılması

Fermer John's inəkləri onun ən böyük örüşündə yerləşmişdir. Bütün örüşü böyük bir 2D xanalı şəbəkə kimi təsəvvür etmək olar (böyük bir şahmat taxtasını düşünün).

İnəklərin örüşdə yerləşmə qaydası olduqca maraqlıdır. Hər bir $(x,y)$ hüceyrəsi üçün, x \ge 0 və y \ge 0 olduqda, $(x,y)$ hüceyrəsində inək mövcuddur, əgər bütün k \ge 0 tam ədədləri üçün \left\lfloor \frac{x}{3^k} \right\rfloor və \left\lfloor \frac{y}{3^k} \right\rfloor ədədlərinin $3$-ə bölünməsindən alınan qalıqların pariteti eynidirsə. Yəni, həm qalıqlar tək (yəni $1$-ə bərabər), ya da hər ikisi cütdür (yəni $0$ və ya $2$-yə bərabər). Məsələn, 0 \le x, y < 9 üçün, inəklərin olduğu hüceyrələr aşağıdakı cədvəldə $1$ ilə işarələnmişdir:

        x
    012345678

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

Fermer John müəyyən diaqonal bölgələrdə neçə inək olduğunu bilmək istəyir. O, $q$ sorğu verir, hər biri x_i, y_i, d_i ədədlərindən ibarətdir. Hər sorğu üçün, fermer John (x_i, y_i)-dən (x_i + d_i, y_i + d_i)-ə (hər iki uç daxil olmaqla) olan diaqonalda neçə inəyin olduğunu bilmək istəyir.