STAND - Gian hàng đặc biệt
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Dũng sống tại một vùng biển du lịch nổi tiếng. Sát bãi biển đẹp nhất có một khu chợ hình chữ nhật kích thước X × Y . Để tiện quản lý, ban quản lý biểu diễn hình chữ nhật đó trên mặt phẳng tọa độ Đề-các x0y với bốn đỉnh hình chữ nhật có tọa độ là (0, 0),(X, 0),(X, Y ),(Y, 0). Trên mỗi điểm tọa độ (a, b), với a ∈ {1, . . . , X}, b ∈ {1, . . . , Y } người ta đặt một gian hàng cho thuê. Là một doanh nhân thành đạt, Dũng nhận thấy nên kinh doanh ở đây bằng cách thuê Q mặt bằng hình chữ nhật có các cạnh song song với các cạnh của khu chợ, và 4 đỉnh thuộc hình chữ nhật tương ứng với khu chợ. Mặt bằng thứ i được xác định bởi hai điểm có tọa độ (SXi , SYi) và (DXi , DYi ), là hai đỉnh đối điện của hình chữ nhật tương ứng. Dũng mong muốn mỗi mặt bằng chứa thật nhiều gian hàng đặc biệt, mỗi gian hàng tương ứng với một điểm, có các đặc điểm sau:

• khoảng cách Ơclit giữa điểm gốc (0, 0) và gian hàng đặc biệt phải là số nguyên;
• không có gian hàng nào nằm trên đoạn thẳng nối điểm gốc (0, 0) với gian hàng đặc biệt đang xét.

Yêu cầu: Với mỗi mặt bằng, hãy tính số lượng gian hàng đặc biệt mà mặt bằng đó chứa, tính cả gian hàng nằm trên cạnh mặt bằng.

Dữ liệu vào

Dòng đầu tiên chứa 3 số nguyên dương X Y Q (2 ≤ X, Y ≤ 7000; Q ≤ 100000) cách nhau bởi dấu cách.
Mỗi dòng trong số Q dòng tiếp theo chứa 4 số nguyên SXi SYi DXi DYi cách nhau bởi dấu cách.

Kết quả

Ghi ra Q dòng, mỗi dòng là kết quả tìm được tương ứng với dữ liệu vào. 

Ví dụ

Input

5 5 2
1 5 3 4
3 4 4 3

Output

1
2

Giải thích:

Trong ví dụ trên,
• mặt bằng thứ nhất chứa duy nhất một gian hàng đặc biệt tại vị trí (3,4);
• mặt bằng thứ hai chứa hai gian hàng đặc biệt tại vị trí (3,4) và (4,3).


Nguồn: ĐPT '1819

Back to Top