Thu Thuế
View as PDFSau chuyến thị sát quanh vương quốc, MH phát hiện rằng hệ thống thu thuế của vương quốc đang không hoạt động hiệu quả và làm thất thoát lượng lớn thuế của vương quốc. Vì vậy, cô quyết định thiết lập lại hệ thống thu thuế, mở đầu bằng việc thống kê. Vương quốc Poinciana là một vùng đất hình chữ nhật kéo dài từ ~(0,0)~ đến ~(W,H)~ trên mặt phẳng tọa độ. Bên trong vương quốc bao gồm ~n~ lãnh địa quý tộc và ~m~ thành phố. Lãnh địa quý tộc thứ i là một mảnh đất hình chữ nhật kéo dài từ ~(X_i,Y_i)~ đến ~(A_i,B_i) (X_i < A_i, Y_i < B_i)~. 2 cạnh bất kì của các lãnh địa không có điểm chung với nhau và cũng không có điểm chung với biên giới vương quốc. Thành phố thứ ~j~ nằm ở vị trí ~(C_j,R_j)~ và có số thuế hàng nằm là ~t_j~. Để tiện cho việc quản lý thì mỗi thành phố sẽ nộp thuế trực tiếp cho quý tộc của vùng lãnh địa nhỏ nhất mà nó nằm trong hoặc hoàng gia nếu không nằm trong vùng lãnh địa quý tộc. Biết không có thành phố nào nằm trên biên giới vương quốc cũng như biên giới lãnh địa, hãy giúp MH tính xem với hoàng gia và từng quý tộc thì số thuế hàng nay thu trực tiếp từ các thành phố là bao nhiêu nhé!
INPUT
- Dòng đầu tiên gồm 4 số nguyên dương ~W,H,n,m~ ~(W,H \leq 10^9,n,m \leq 10^5)~
- ~n~ dòng tiếp theo, dòng thứ ~i~ gồm 4 số ~X_i, Y_i, A_i, B_i( 0 < X_i, A_i < W,0 < Y_i, B_i < H)~ tọa độ góc trái dưới và phải trên của từng lãnh địa.
- ~m~ dòng còn lại, dòng thứ ~j~ gồm 3 số ~C_j,R_j,t_j~ tọa độ của thành phố thứ ~j~ và số thuế hàng năm.
OUTPUT
- Gồm ~n+1~ số in trên 1 dòng, số thứ ~i~ là lượng thuế hàng năm quý tộc thứ ~i~ thu và số thứ ~n+1~ là lượng thuế hàng năm hoàng gia thu.
Sample Input
10 8 3 7
1 1 6 7
7 1 9 4
2 4 5 6
2 2 7
5 3 9
7 5 15
3 5 4
8 3 7
9 7 5
8 2 10
Sample Output
16 17 4 20
Subtask
- Subtask 1: ~n,m \leq 10^3~ (~20p~).
- Subtask 2: ~W,H \leq 10^3~ (~30p~).
- Subtask 3: không ràng buộc (~20p~).
Comments
Bộ test đã được thay đổi
https://ideone.com/BRdrFV