Tô màu (THTB N.An 2021)

Xem PDF




Thời gian:
Python 3 5.0s

Tác giả:
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Lớp Hồng đang chơi trò tô màu trên bảng số. Các bạn kẻ một bảng số hình chữ nhật gồm \(N\) dòng và \(M\) cột. Các hàng được đánh số từ 1 đến \(N\), từ trên xuống dưới; các cột được đánh số từ 1 đến \(M\), từ trái sang phải. Ô ở hàng thứ \(i\) và cột thứ \(j\) được gọi là ô (\(i\),\(j\)) và được điền giá trị là \(i\) × \(j\). Có \(K\) bạn tham gia chơi trò chơi, mỗi bạn chọn một hình chữ nhật trên bảng số và tô bằng một màu mà mình thích (các hình chữ nhật của các bạn có thể đè lên nhau – tô đè lên).

Yêu cầu: Cho \(N, M\) là kích thước bảng số và \(K\) hình chữ nhật được mô tả bằng ô trái trên và ô phải dưới. Hãy tỉnh tổng những ô chưa được tô màu trên bảng số.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

  • Dòng đầu chứa ba số nguyên \(N, M, K\) mô tả kích thước của bảng số và số lượng hình chữ nhật được tô màu;
  • \(K\) dòng sau, mỗi dòng chứa bốn số nguyên \(x, y, u, v\) mô tả ô trái trên (\(x, y\)) và ô phải dưới (\(u, v\)) của một hình chữ nhật. Các ô thoả mãn mô tả một hình chữ nhật nằm trong bảng số.

Output

  • Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là phần dư của phép chia của tổng các ô chưa được tô màu trên bảng số cho \(10^9 + 7\).

Scoring

  • Subtask #1 (\(20\%\) số điểm): \(K = 1; N, M \leq 100\);
  • Subtask #2 (\(10\%\) số điểm): \(K = 1; N, M \leq 10^6\);
  • Subtask #3 (\(10\%\) số điểm): \(K = 1; N, M \leq 10^9\);
  • Subtask #4 (\(10\%\) số điểm): \(K = 10; N, M \leq 100\);
  • Subtask #5 (\(20\%\) số điểm): \(K = 2; N, M \leq 10^6\);
  • Subtask #6 (\(10\%\) số điểm): \(K = 2; N, M \leq 10^9\);
  • Subtask #7 (\(10\%\) số điểm): \(K = 3; N, M \leq 10^9\);
  • Subtask #8 (\(10\%\) số điểm): \(K \leq 10; N, M \leq 10^9\).

Example

Test 1

Input
3 3 2
1 2 3 3
3 1 3 2
Output
3
Note

Còn 2 ô chưa bị tô màu là ô (1,1) và ô (2,1). Vậy tổng là 1 + 2 = 3.


Bình luận

Không có bình luận nào.