Đất nước JOI có dạng một tam giác đều cạnh \(L\), với ba đỉnh \(A\), \(B\), \(C\), trong đó \(L\) là số nguyên dương. Cạnh \(AB\) nằm theo hướng Đông - Tây: \(A\) là điểm cực Tây, \(B\) là điểm cực Đông, còn \(C\) là điểm cực Bắc của đất nước.

Đất nước được chia thành \(L^2\) vùng tam giác đều cạnh \(1\). Một điểm là đỉnh của một vùng được gọi là điểm lưới. Với các số nguyên \(x,y\) thỏa mãn \(0 \le y \le L\) và \(0 \le x \le L-y\), điểm lưới ở hàng thứ \(1+y\) tính từ phía Nam và là điểm thứ \(1+x\) tính từ phía Tây trong hàng đó được ký hiệu là \((x,y)\). Đặc biệt, \(A\), \(B\), \(C\) lần lượt là \((0,0)\), \((L,0)\), \((0,L)\). Hình dưới minh họa các vùng và điểm lưới khi \(L=5\).

Hình 1: Các vùng tam giác và điểm lưới khi \(L=5\).

Dự báo thời tiết cho \(N\) ngày tiếp theo đã được công bố. Trong ngày thứ \(i\), mưa sẽ rơi trên tam giác có ba đỉnh lưới \((X_i, Y_i)\), \((X_i + Z_i, Y_i)\) và \((X_i, Y_i + Z_i)\). Một vùng tam giác nhỏ được xem là có mưa trong ngày \(i\) nếu toàn bộ vùng đó nằm trong tam giác dự báo.

Để chuẩn bị ứng phó với thiên tai do mưa gây ra, với mỗi \(k = 1, 2, \ldots, K\), cần xác định số vùng được dự báo có mưa trong ít nhất \(k\) ngày. Cho kích thước đất nước, dự báo thời tiết và \(K\), hãy tính các số lượng này.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(L\), \(N\), \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(X_i\), \(Y_i\), \(Z_i\).

Dữ liệu ra

In ra \(K\) dòng. Dòng thứ \(k\) chứa số vùng được dự báo có mưa trong ít nhất \(k\) ngày.

Ràng buộc

• \(2 \le L \le 10^9\).
• \(2 \le N \le 200000\).
• \(1 \le K \le 5\).
• \(0 \le X_i, Y_i \le L\).
• \(1 \le Z_i \le L\).
• \(X_i + Y_i + Z_i \le L\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(N = 2\), \(K = 2\).
• Nhóm 2 (5 điểm): \(L \le 100\), \(N \le 100\).
• Nhóm 3 (5 điểm): \(L \le 1000\).
• Nhóm 4 (7 điểm): \(N \le 2000\).
• Nhóm 5 (10 điểm): \(X_i = 0\) với mọi \(1 \le i \le N\), \(K = 1\).
• Nhóm 6 (10 điểm): \(X_i = 0\) với mọi \(1 \le i \le N\).
• Nhóm 7 (23 điểm): \(K = 1\).
• Nhóm 8 (18 điểm): \(K \le 2\).
• Nhóm 9 (18 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 2 2
1 0 3
0 1 4

21
4

5 4 5
1 0 4
0 1 3
2 0 2
1 2 2

21
10
2
0
0

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Triangular Rainfall. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.