Negara IOI memutuskan untuk membangun jaringan transportasinya secara menyeluruh. Negara IOI dinyatakan sebagai bidang koordinat $xy$, dan terdapat $N$ kota di atasnya. Kota ke-$i$ ($1\le i\le N$) dinyatakan sebagai titik $(X_i,Y_i)$. Jaringan transportasi dibangun dengan langkah-langkah berikut.

• Bangun bandara internasional di beberapa dari $N$ kota. Setidaknya satu bandara internasional harus dibangun. Setiap bandara internasional memerlukan biaya tetap untuk dibangun.
• Bangun sejumlah jalan yang menghubungkan kota-kota. Setiap jalan adalah ruas garis sejajar sumbu $x$ atau sumbu $y$ yang langsung menghubungkan titik-titik yang menyatakan kota. Biaya membangun satu jalan sama dengan panjangnya.

Syarat-syarat berikut harus dipenuhi.

• Terdapat $M$ wilayah di negara IOI yang tidak dapat dibangun jalan karena kondisi tanah yang buruk atau alasan lain. Setiap wilayah dinyatakan sebagai persegi panjang. Sudut kiri bawah persegi panjang ke-$j$ ($1\le j\le M$) adalah $(P_j,Q_j)$ dan sudut kanan atasnya adalah $(R_j,S_j)$, sehingga $P_j<R_j$ dan $Q_j<S_j$. Tidak boleh ada jalan yang memiliki bagian persekutuan dengan salah satu dari $M$ wilayah tersebut. Wilayah mencakup batasnya, sehingga tidak boleh ada jalan yang memiliki bagian persekutuan dengan batas persegi panjang wilayah tersebut.
• Dari setiap kota di antara $N$ kota, harus dimungkinkan mencapai kota yang memiliki bandara internasional dengan berulang kali mengikuti jalan menuju kota lain.

Terdapat $C$ perusahaan konstruksi yang menjadi calon kontraktor proyek ini. Perusahaan ke-$k$ ($1\le k\le C$) memerlukan biaya $B_k$ untuk membangun satu bandara internasional dan dapat membangun paling banyak $H_k$ bandara internasional. Biaya pembangunan jalan tidak bergantung pada perusahaan, dan tidak ada batasan jumlah maupun panjang jalan. Untuk setiap perusahaan, kita ingin menentukan nilai minimum total biaya yang diperlukan perusahaan tersebut untuk membangun jaringan transportasi yang memenuhi syarat-syarat di atas.

Mungkin ada perusahaan yang tidak dapat membangun jaringan transportasi yang memenuhi syarat karena jumlah bandara internasional yang dapat dibangunnya terlalu sedikit. Dalam hal tersebut, laporkan bahwa syarat tidak dapat dipenuhi, sebagai pengganti total biaya.

Tugas

Diberikan bilangan bulat $N$ yang menyatakan jumlah kota di negara IOI beserta koordinat kota-kota, bilangan bulat $M$ yang menyatakan jumlah wilayah yang tidak dapat dibangun jalan beserta koordinat tiap wilayah, serta bilangan bulat $C$ yang menyatakan jumlah calon perusahaan kontraktor beserta informasi tiap perusahaan. Buatlah program yang menentukan, untuk setiap perusahaan, nilai minimum total biaya pembangunan jaringan transportasi yang memenuhi syarat dalam pernyataan soal.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama berisi tiga bilangan bulat $N,M,C$ yang dipisahkan oleh spasi, masing-masing menyatakan jumlah kota di negara IOI, jumlah wilayah yang tidak dapat dibangun jalan, dan jumlah calon perusahaan kontraktor.
• Baris ke-$i$ dari $N$ baris berikutnya ($1\le i\le N$) berisi dua bilangan bulat $X_i,Y_i$ yang dipisahkan oleh spasi, menyatakan bahwa koordinat kota ke-$i$ adalah $(X_i,Y_i)$.
• Baris ke-$j$ dari $M$ baris berikutnya ($1\le j\le M$) berisi empat bilangan bulat $P_j,Q_j,R_j,S_j$ yang dipisahkan oleh spasi. Ini menyatakan bahwa persegi panjang wilayah ke-$j$ yang tidak dapat dibangun jalan memiliki sudut kiri bawah $(P_j,Q_j)$ dan sudut kanan atas $(R_j,S_j)$.
• Baris ke-$k$ dari $C$ baris berikutnya ($1\le k\le C$) berisi dua bilangan bulat $B_k,H_k$ yang dipisahkan oleh spasi. Ini menyatakan bahwa calon perusahaan ke-$k$ memerlukan biaya $B_k$ untuk membangun satu bandara internasional dan dapat membangun paling banyak $H_k$ bandara internasional.

Keluaran

Tuliskan $C$ baris ke keluaran standar. Pada baris ke-$k$ ($1\le k\le C$), tuliskan sebuah bilangan bulat yang menyatakan nilai minimum total biaya jika calon perusahaan ke-$k$ melaksanakan proyek ini. Jika perusahaan ke-$k$ tidak dapat melaksanakan proyek dengan memenuhi syarat, tuliskan bilangan bulat $-1$ sebagai gantinya.

Batasan

Semua data masukan memenuhi syarat-syarat berikut.

• $1\le N\le 200\,000$.
• $1\le M\le 200\,000$.
• $1\le C\le 500\,000$.
• $0\le X_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $0\le Y_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• Tidak ada dua kota atau lebih yang berada pada koordinat yang sama.
• $0\le P_j<R_j\le 1\,000\,000\,000$ ($1\le j\le M$).
• $0\le Q_j<S_j\le 1\,000\,000\,000$ ($1\le j\le M$).
• Tidak ada wilayah yang mengandung kota di dalam ataupun pada batas persegi panjangnya.
• $1\le B_k\le 1\,000\,000\,000$ ($1\le k\le C$).
• $1\le H_k\le N$ ($1\le k\le C$).

Subsoal

Subsoal 1 [10 poin]

Memenuhi syarat-syarat berikut.

• $M\le 100$.
• $C\le 100$.

Subsoal 2 [30 poin]

Memenuhi syarat-syarat berikut.

• $C\le 100$.

Subsoal 3 [30 poin]

Memenuhi syarat-syarat berikut.

• $M\le 100$.

Subsoal 4 [30 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 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

Keluaran 1

28
38
-1

Penjelasan

Masukan ini digambarkan seperti berikut. Persegi panjang bergaris tebal menunjukkan wilayah yang tidak dapat dibangun jalan.

Jalan yang menghubungkan kota $2$ dengan kota $4$ serta kota $3$ dengan kota $4$ dapat dibangun. Namun, jalan antara kota $1$ dan kota $2$ tidak dapat dibangun karena akan berpotongan dengan wilayah terlarang. Demikian pula, jalan antara kota $1$ dan kota $3$ tidak dapat dibangun. Perhatikan bahwa jalan juga tidak boleh memiliki bagian persekutuan dengan batas persegi panjang.

Perusahaan pertama dapat membangun paling banyak $4$ bandara internasional dengan biaya $7$ per bandara. Dalam hal ini, pilihan terbaik adalah membangun bandara internasional di semua kota tanpa membangun jalan sama sekali. Total biayanya adalah $7\times 4=28$.

Perusahaan kedua dapat membangun paling banyak $3$ bandara internasional dengan biaya $10$ per bandara. Dalam hal ini, salah satu pilihan terbaik adalah membangun jalan sepanjang $9$ yang menghubungkan kota $2$ dengan kota $4$ dan jalan sepanjang $9$ yang menghubungkan kota $3$ dengan kota $4$, lalu membangun bandara internasional di kota $1$ dan kota $2$. Total biayanya adalah $10\times 2+9+9=38$.

Perusahaan ketiga dapat membangun paling banyak $1$ bandara internasional dengan biaya $1$ per bandara. Namun, karena tidak ada jalan yang dapat dibangun antara kota $1$ dan kota lain mana pun, diperlukan setidaknya $2$ bandara internasional untuk memenuhi syarat dalam pernyataan soal. Dengan demikian, perusahaan ini tidak dapat melaksanakan proyek, sehingga keluarkan $-1$.