Cho một bảng có kích thước vô hạn, các hàng và các cột đánh số từ 0.

Ô ở hàng \(x\) cột \(y\) được gọi là ô \((x, y)\) và có giá trị là \(\begin{cases}1 & \text{nếu}\ \forall k: \lfloor\frac{x}{3^k}\rfloor \text{mod}\ 2 = \lfloor\frac{y}{3^k}\rfloor \text{mod}\ 2\\ 0 & \text{nếu ngược lại}\end{cases}\)

Sau đây là \(9 \times 9\) ô đầu tiên của bảng:

        x
    012345678

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

Có \(Q\) truy vấn có dạng \((d_i, x_i, y_i)\). Với mỗi truy vấn thứ \(i\), bạn cần trả lời tổng các số nằm trên đường chéo \((x_i, y_i), (x_i+1, y_i+1), (x_i+2, y_i+2), \dots, (x_i+d_i, y_i+d_i)\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(Q\) \((1 \leq Q \leq 10^4)\)
• \(Q\) dòng tiếp theo, dòng thứ \(i\) lần lượt chứa ba số \(d_i, x_i, y_i\) \((0 \leq x_i, y_i, d_i \leq 10^{18})\)

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Điểm số

• Test 1 là test ví dụ
• Test 2 thỏa mãn \(d_i \leq 100\) với mỗi truy vấn.
• Test 3-6 thỏa mãn \(x_i+d_i = 3^{30}-1; y=0\) với mỗi truy vấn.
• Test 7-12 không có điều kiện nào khác.

Ví dụ

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

Cho một chuồng rộng vô hạn được biểu diễn dưới dạng lưới 2D. Có một tập hợp lớn gồm \(N\) con bò, con bò thứ \(i\) đứng ở hàng \(x_i\) cột \(y_i\) (ký hiệu là ô \((x_i, y_i)\)).

Một cách đặt hàng rào sẽ bao đóng trọn vẹn một vùng chữ nhật các ô, với các cạnh phải song song với trục \(x\) và \(y\), vùng có thể nhỏ tới mức chỉ bao gồm một ô.

Với một cách đặt hàng rào, có thể dựng nên một tập hợp con các con bò nằm trong hàng rào.

Đếm số tập con khác nhau của tập hợp lớn có thể xây dựng bằng cách đặt hàng rào như trên.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(N\) \((1 \leq N \leq 2500)\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(x_i, y_i\) \((0 \leq x_i, y_i \leq 10^9)\)

Định dạng đầu ra

• In ra số tập con khác nhau có thể dựng được

Điểm số

• Test 1 là test ví dụ
• Test 2-3 thỏa mãn \(N \leq 20\)
• Test 4-6 thỏa mãn \(N \leq 100\)
• Test 7-12 thỏa mãn \(N \leq 500\)
• Test 13-20 không có điều kiện nào khác.

Ví dụ

4
0 2
1 0
2 3
3 5

13

💫Đề bài: An đang gặp một bài toán rất nổi tiếng trên mạng. An không biết cách giải thế nào đành nhớ các coder. Các coder thông minh hãy giải bài toán này nhé!

🧩Mission: Hãy giải bài toán nổi tiếng trên với n là một số nguyên (Giới hạn: n < 10^15)
📥Input: Một số nguyên là n (n \(1015\))
📤Output: Kết quả của bài toán.

🧪Ví dụ: