Đất nước IOI quyết định đồng loạt xây dựng mạng lưới giao thông. Đất nước được biểu diễn bằng mặt phẳng tọa độ $xy$, trên đó có $N$ thị trấn. Thị trấn thứ $i$ ($1\le i\le N$) được biểu diễn bởi điểm $(X_i,Y_i)$. Việc xây dựng mạng lưới được tiến hành như sau.

• Xây sân bay quốc tế tại một số trong $N$ thị trấn. Phải xây ít nhất một sân bay quốc tế. Mỗi sân bay có một chi phí xây dựng cố định.
• Xây một số con đường nối các thị trấn. Mỗi con đường là một đoạn thẳng song song với trục $x$ hoặc trục $y$, nối trực tiếp hai điểm biểu diễn hai thị trấn. Chi phí xây một con đường bằng độ dài của nó.

Phải thỏa mãn các điều kiện sau.

• Có $M$ vùng không thể xây đường do nền đất yếu hoặc các nguyên nhân khác. Mỗi vùng là một hình chữ nhật; hình chữ nhật thứ $j$ ($1\le j\le M$) có đỉnh dưới bên trái $(P_j,Q_j)$ và đỉnh trên bên phải $(R_j,S_j)$ (tức là $P_j<R_j$ và $Q_j<S_j$). Không con đường nào được có điểm chung với bất kỳ vùng nào trong $M$ vùng. Các vùng bao gồm cả biên, nên đường cũng không được có điểm chung với chu vi hình chữ nhật.
• Từ mỗi thị trấn trong $N$ thị trấn, phải có thể liên tiếp đi theo đường đến các thị trấn khác để tới một thị trấn có sân bay quốc tế.

Có $C$ công ty xây dựng được xem xét để nhận dự án. Công ty thứ $k$ ($1\le k\le C$) cần chi phí $B_k$ để xây một sân bay quốc tế và có thể xây nhiều nhất $H_k$ sân bay (chi phí xây đường không phụ thuộc công ty, và không có giới hạn về số lượng hay độ dài đường). Với mỗi công ty, ta muốn tìm tổng chi phí nhỏ nhất để xây mạng lưới giao thông thỏa mãn các điều kiện trên.

Một số công ty có thể không thực hiện được dự án thỏa mãn các điều kiện vì số sân bay được phép xây quá ít. Trong trường hợp đó, hãy báo rằng không thể thỏa mãn các điều kiện thay vì báo tổng chi phí.

Nhiệm vụ

Cho số thị trấn $N$ và tọa độ của chúng, số vùng cấm xây đường $M$ và tọa độ mô tả từng vùng, số công ty ứng viên $C$ và thông tin của từng công ty. Hãy viết chương trình tìm, với mỗi công ty, tổng chi phí nhỏ nhất để xây mạng lưới giao thông thỏa mãn các điều kiện trong đề bài.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa ba số nguyên $N,M,C$, cách nhau bởi dấu cách, lần lượt là số thị trấn ở đất nước IOI, số vùng không thể xây đường và số công ty ứng viên nhận dự án.
• Dòng thứ $i$ ($1\le i\le N$) trong $N$ dòng tiếp theo chứa hai số nguyên $X_i,Y_i$, cách nhau bởi dấu cách, biểu thị tọa độ $(X_i,Y_i)$ của thị trấn thứ $i$.
• Dòng thứ $j$ ($1\le j\le M$) trong $M$ dòng tiếp theo chứa bốn số nguyên $P_j,Q_j,R_j,S_j$, cách nhau bởi dấu cách, biểu thị đỉnh dưới bên trái $(P_j,Q_j)$ và đỉnh trên bên phải $(R_j,S_j)$ của hình chữ nhật mô tả vùng cấm xây đường thứ $j$.
• Dòng thứ $k$ ($1\le k\le C$) trong $C$ dòng tiếp theo chứa hai số nguyên $B_k,H_k$, cách nhau bởi dấu cách. Công ty ứng viên thứ $k$ cần chi phí $B_k$ để xây một sân bay quốc tế và có thể xây nhiều nhất $H_k$ sân bay.

Dữ liệu ra

Ghi $C$ dòng ra đầu ra chuẩn. Dòng thứ $k$ ($1\le k\le C$) chứa một số nguyên là tổng chi phí nhỏ nhất nếu công ty ứng viên thứ $k$ thực hiện dự án. Nếu công ty đó không thể thực hiện dự án thỏa mãn các điều kiện, hãy ghi số nguyên $-1$ thay thế.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $1\le N\le200\,000$.
• $1\le M\le200\,000$.
• $1\le C\le500\,000$.
• $0\le X_i\le1\,000\,000\,000$ ($1\le i\le N$).
• $0\le Y_i\le1\,000\,000\,000$ ($1\le i\le N$).
• Không có hai thị trấn trở lên tại cùng một tọa độ.
• $0\le P_j<R_j\le1\,000\,000\,000$ ($1\le j\le M$).
• $0\le Q_j<S_j\le1\,000\,000\,000$ ($1\le j\le M$).
• Không hình chữ nhật mô tả vùng cấm nào chứa thị trấn ở bên trong hoặc trên biên.
• $1\le B_k\le1\,000\,000\,000$ ($1\le k\le C$).
• $1\le H_k\le N$ ($1\le k\le C$).

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

Thỏa mãn các điều kiện sau.

• $M\le100$.
• $C\le100$.

Nhiệm vụ con 2 [30 điểm]

Thỏa mãn các điều kiện sau.

• $C\le100$.

Nhiệm vụ con 3 [30 điểm]

Thỏa mãn các điều kiện sau.

• $M\le100$.

Nhiệm vụ con 4 [30 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

Dữ liệu ra 1

28
38
-1

Ghi chú

Ví dụ này được minh họa trong hình dưới đây. Các hình chữ nhật nét đậm biểu thị các vùng không thể xây đường.

Có thể xây đường nối thị trấn 2 với thị trấn 4 và thị trấn 3 với thị trấn 4, nhưng không thể xây đường giữa thị trấn 1 và thị trấn 2 vì đường sẽ giao với vùng cấm. Tương tự, không thể xây đường giữa thị trấn 1 và thị trấn 3 (lưu ý rằng đường cũng không được có điểm chung với chu vi hình chữ nhật).

Công ty thứ nhất có thể xây nhiều nhất 4 sân bay quốc tế, mỗi sân bay có chi phí $7$. Trong trường hợp này, phương án tốt nhất là không xây đường nào mà xây sân bay tại tất cả các thị trấn. Tổng chi phí là $7\times4=28$.

Công ty thứ hai có thể xây nhiều nhất 3 sân bay quốc tế, mỗi sân bay có chi phí $10$. Trong trường hợp này, một phương án tốt nhất là xây hai con đường dài $9$ nối thị trấn 2 với thị trấn 4 và thị trấn 3 với thị trấn 4, rồi xây sân bay tại thị trấn 1 và thị trấn 2. Tổng chi phí là $10\times2+9+9=38$.

Công ty thứ ba có thể xây nhiều nhất 1 sân bay quốc tế với chi phí $1$ cho mỗi sân bay. Tuy nhiên, không thể xây đường nối thị trấn 1 với bất kỳ thị trấn nào khác, nên phải xây ít nhất 2 sân bay để thỏa mãn các điều kiện. Vì vậy công ty này không thể thực hiện dự án và ta ghi $-1$.