Vũ và Việt mỗi người có một tập hợp các điểm có toạ độ thực trên mặt phẳng ~Oxy~, và mỗi tập đều là hợp của một số hình chữ nhật (có thể giao nhau). Mỗi người sẽ chọn hai điểm trong tập của mình một cách độc lập và ngẫu nhiên~^\dagger~. Nhiệm của bạn là tính giá trị kỳ vọng của khoảng cách Manhattan~^\ddagger~ giữa hai điểm được chọn.
~^\dagger~ Việc chọn ngẫu nhiên các điểm thoả mãn phân bố đều liên tục.
~^\ddagger~ Khoảng cách Manhattan giữa hai điểm ~(x_1,y_1)~ và ~(x_2,y_2)~ được định nghĩa là ~|x_1-x_2|+|y_1-y_2|~.
Input
Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~n,m\le 10^5~) — số hình chữ nhật lần lượt tạo nên tập điểm của Vũ và Việt.
Mỗi dòng trong ~n+m~ dòng tiếp theo gồm bốn số nguyên ~x_1,y_1,x_2,y_2~ (~-10^9\le x_1\le x_2\le 10^9~, ~-10^9\le y_1\le y_2\le 10^9~) — toạ độ đỉnh trái dưới ~(x_1,y_1)~ và phải trên ~(x_2,y_2)~ của hình chữ nhật. ~n~ hình chữ nhật đầu tiên và phần còn lại tạo nên lần lượt tập điểm của Vũ và Việt.
Các hình chữ nhật đã cho có thể suy biến. Cụ thể:
Nếu ~x_1=x_2~ hoặc ~y_1=y_2~ thì hình chữ nhật suy biến thành một đoạn thẳng.
Nếu ~x_1=x_2~ và ~y_1=y_2~ thì hình chữ nhật suy biến thành một điểm.
Output
In ra một dòng duy nhất chứa đáp án của bài toán chia dư cho ~10^9 + 7~. Cụ thể, gọi ~\frac{p}{q}~ là phân số tối giản biểu diễn kết quả, in ra ~ans~ sao cho ~ans \equiv \frac{p}{q} \pmod {10^9 + 7}~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20~ | Các hình chữ nhật có dạng suy biến thành điểm |
2 | ~20~ | ~n, m~ và trị tuyệt đối các tọa độ không vượt quá 1000 |
3 | ~60~ | Không có ràng buộc gì thêm |
Sample Input 1
1 1
0 0 0 0
1 1 1 1
Sample Output 1
2
Sample Input 2
1 1
2 0 2 4
0 2 4 2
Sample Output 2
2
Sample Input 3
1 1
0 0 1 1
1 1 2 2
Sample Output 3
2
Bình luận