Hồi kết của Evangelion

Vào năm 2039 (2 năm sau sự kiện Chấn động thứ Hai - Second Impact), loài người đã ngăn chặn thành công các thực thể Angel bằng các cỗ máy chiến đấu Evangelion. Tuy nhiên, loài người không dừng lại ở đó; một số tổ chức muốn sử dụng vũ khí Eva cho các hoạt động quân sự, chiến tranh và xâm lược. Do đó, trong hơn 5 năm tiếp theo, hàng trăm cỗ máy Eva đã được sản xuất và phát động chiến tranh trên toàn thế giới.

Năm 2045, căn cứ quân sự tối mật NERV (nơi chế tạo ra cỗ máy Eva đầu tiên) nhận thấy Trái Đất đang trên bờ vực diệt vong, vì vậy họ đã lên kế hoạch tiêu diệt toàn bộ các cỗ máy Eva trong chiến dịch phòng thủ cuối cùng này. Họ sử dụng chiến hạm không gian tối tân nhất mang tên AAA Wunder để chiến đấu với những cỗ máy Eva còn lại. Tàu AAA Wunder này có hình dáng tương tự một trạm không gian và đã được điều động vào tầng khí quyển; vũ khí chính của tàu là ngọn giáo Longinus đặt trên đỉnh mũi tàu, có khả năng bắn đồng thời 3 tia từ khí quyển xuống mặt đất và tạo ra các vụ nổ khủng khiếp trên toàn bộ khu vực tam giác được tạo bởi 3 tia đó.

Chiến trường là một khu vực bằng phẳng rộng lớn. Để đơn giản hóa, hãy coi chiến trường là một ma trận kích thước $N \times M$ ($N$ hàng và M cột), trên đó gồm các điểm nguyên $(i, j)$ thỏa mãn $(1 \leq i \leq N+1)$ và $(1 \leq j \leq M+1)$.

Tuy nhiên, tàu AAA Wunder có một số hạn chế như sau:

• Các tia bắn ra chỉ có thể đánh trúng các điểm nguyên. Nói cách khác, các điểm $(i, j)$ bị bắn trúng phải thỏa mãn $(1 \leq i \leq N+1)$ và $(1 \leq j \leq M+1)$.
• Khu vực tạo bởi 3 tia bắn đó phải có diện tích lớn hơn 0 (tức 3 điểm bị bắn không thẳng hàng); nếu diện tích bằng 0 thì đòn tấn công sẽ không gây ra sát thương.
• Do tàu AAA Wunder di chuyển trong không phận của chiến trường (ma trận $N \times M$), các tia bắn từ ngọn giáo Longinus không thể bắn trúng vị trí mà tàu AAA Wunder đang bay bên trên.

Chiến dịch này được điều hành bởi siêu máy tính Magi. Để có thể đưa ra chiến lược tối ưu nhất cho chiến dịch, Magi cần giải quyết bài toán sau:

Cho trước tọa độ $(p_i, p_j)$ nơi tàu AAA Wunder đang bay bên trên, hãy tính xem có bao nhiêu cách sử dụng ngọn giáo Longinus xuống chiến trường. Hai cách bắn được coi là khác nhau nếu tập hợp tọa độ của 3 điểm bị bắn khác nhau (không phân biệt thứ tự giữa các tia).

Bạn là Chỉ huy Thuật toán Chiến hạm (Battleship Algorithm Commander) của tàu AAA Wunder. Hãy lập trình giải thuật giải quyết bài toán trên và bàn giao cho siêu máy tính Magi.

Đầu vào:

• Dòng đầu tiên chứa hai số nguyên $N, M$ $(1 \leq N, M \leq 1000)$.
• Dòng thứ hai chứa số nguyên q $(1 \leq q \leq 10)$, số lượng truy vấn mà Magi cần thực hiện.
• Trong q dòng tiếp theo, mỗi dòng chứa hai số nguyên p_i và p_j $(1 \leq p_i \leq N + 1,$ $1 \leq p_j \leq M + 1)$.

Đầu ra:

• Gồm q dòng, mỗi dòng là một số nguyên biểu thị số cách bắn tương ứng với từng truy vấn.

Subtask (tham khảo)

• $33\%$ số test có $1 \leq N, M \leq 10$.
• $67\%$ số test còn lại có giới hạn như mô tả trong đề bài.

Ví dụ 1:

Đầu vào:

2 4
2
2 2
1 4

Đầu ra:

330
329