قررت دولة IOI تطوير شبكة النقل بأكملها. تُمثل الدولة بالمستوى الإحداثي $xy$، وتوجد عليه $N$ بلدة. تُمثل البلدة $i$ ($1 \le i \le N$) بالنقطة $(X_i,Y_i)$. يجري تطوير شبكة النقل وفق الخطوات التالية.

• تُبنى مطارات دولية في بعض البلدات $N$. يجب بناء مطار دولي واحد على الأقل. وتوجد تكلفة ثابتة لبناء كل مطار دولي.
• تُنشأ بعض الطرق التي تصل بين البلدات. كل طريق قطعة مستقيمة تصل مباشرة بين نقطتين تمثلان بلدتين، وتوازي محور $x$ أو محور $y$. تكلفة إنشاء كل طريق تساوي طوله.

يجب أن تتحقق الشروط التالية.

• توجد في دولة IOI مناطق عددها $M$ لا يمكن إنشاء الطرق فيها بسبب سوء التربة أو أسباب أخرى. تُمثل كل منطقة بمستطيل، والزاوية السفلية اليسرى للمستطيل $j$ ($1 \le j \le M$) هي $(P_j,Q_j)$ والزاوية العلوية اليمنى هي $(R_j,S_j)$، أي $P_j<R_j$ و$Q_j<S_j$. يجب ألا يشترك أي طريق في أي نقطة مع أي من هذه المناطق $M$. تشمل المنطقة حدودها، ولذلك لا يُسمح أيضًا بطريق يلتقي بحدود أحد المستطيلات.
• يجب أن يكون من الممكن الوصول من كل بلدة من البلدات $N$ إلى بلدة تحتوي على مطار دولي، بتكرار الانتقال إلى بلدات أخرى عبر الطرق.

تُرشح $C$ شركة بناء لتنفيذ هذا المشروع. الشركة $k$ ($1 \le k \le C$) تتقاضى تكلفة $B_k$ لبناء مطار دولي واحد، ويمكنها بناء $H_k$ مطارًا دوليًا على الأكثر. لا تعتمد تكلفة إنشاء الطرق على الشركة، ولا توجد قيود على عدد الطرق أو أطوالها. نريد، لكل شركة، معرفة أقل تكلفة إجمالية لتطوير شبكة النقل بحيث تتحقق الشروط السابقة.

قد توجد شركة لا تستطيع تنفيذ شبكة نقل تحقق الشروط، لأن الحد الأقصى لعدد المطارات التي تستطيع بناءها صغير جدًا. في هذه الحالة، نريد الإبلاغ عن استحالة تحقيق الشروط بدلًا من إعطاء تكلفة إجمالية.

المهمة

بمعرفة العدد الصحيح $N$ الذي يمثل عدد بلدات IOI وإحداثياتها، والعدد الصحيح $M$ الذي يمثل عدد المناطق المحظورة وإحداثيات كل منها، والعدد الصحيح $C$ الذي يمثل عدد شركات البناء المرشحة ومعلوماتها، اكتب برنامجًا يحسب لكل شركة أقل تكلفة إجمالية لتطوير شبكة النقل بما يحقق الشروط الواردة في نص المسألة.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على ثلاثة أعداد صحيحة $N,M,C$، مفصولة بمسافات، وتمثل على الترتيب عدد بلدات IOI وعدد المناطق التي يُحظر فيها إنشاء الطرق وعدد شركات البناء المرشحة.
• يحتوي السطر $i$ ($1 \le i \le N$) من الأسطر $N$ التالية على عددين صحيحين $X_i,Y_i$ مفصولين بمسافة، ويمثلان إحداثيات البلدة $i$، أي $(X_i,Y_i)$.
• يحتوي السطر $j$ ($1 \le j \le M$) من الأسطر $M$ التالية على أربعة أعداد صحيحة $P_j,Q_j,R_j,S_j$، مفصولة بمسافات. تمثل $(P_j,Q_j)$ الزاوية السفلية اليسرى و$(R_j,S_j)$ الزاوية العلوية اليمنى للمستطيل الذي يصف المنطقة المحظورة $j$.
• يحتوي السطر $k$ ($1 \le k \le C$) من الأسطر $C$ التالية على عددين صحيحين $B_k,H_k$ مفصولين بمسافة، ويعنيان أن الشركة المرشحة $k$ تتقاضى تكلفة $B_k$ لبناء مطار دولي واحد، ويمكنها بناء $H_k$ مطارًا دوليًا على الأكثر.

الإخراج

اطبع $C$ سطرًا في الإخراج القياسي. في السطر $k$ ($1 \le k \le C$)، اطبع عددًا صحيحًا واحدًا يمثل أقل تكلفة إجمالية إذا نفذت الشركة المرشحة $k$ المشروع. وإذا لم تستطع تلك الشركة تنفيذ المشروع مع تحقيق الشروط، فاطبع بدلًا من ذلك العدد الصحيح -1.

القيود

تستوفي جميع بيانات الإدخال الشروط التالية.

• $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$).
• لا توجد بلدتان أو أكثر في الموضع نفسه.
• $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$).
• لا تحتوي أي منطقة على بلدة داخل مستطيلها أو على حدوده.
• $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$).

المهام الفرعية

المهمة الفرعية 1 [10 نقاط]

تتحقق الشروط التالية.

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

المهمة الفرعية 2 [30 نقطة]

تتحقق الشروط التالية.

• $C \le 100$.

المهمة الفرعية 3 [30 نقطة]

تتحقق الشروط التالية.

• $M \le 100$.

المهمة الفرعية 4 [30 نقطة]

لا توجد قيود إضافية.

أمثلة

الإدخال 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

الإخراج 1

28
38
-1

ملاحظة

يوضح الشكل التالي هذا المثال. تشير المستطيلات ذات الحدود السميكة إلى المناطق التي يُحظر فيها إنشاء الطرق.

يمكن إنشاء طريق بين البلدتين $2$ و$4$ وطريق بين البلدتين $3$ و$4$، لكن لا يمكن إنشاء طريق بين البلدتين $1$ و$2$ لأنه سيتقاطع مع منطقة محظورة. وبالمثل، لا يمكن إنشاء طريق بين البلدتين $1$ و$3$. لاحظ أن الطرق لا يجوز أن تشترك حتى في نقطة مع حدود المستطيلات.

يمكن للشركة الأولى بناء 4 مطارات دولية على الأكثر بتكلفة $7$ لكل مطار. في هذه الحالة، الأفضل هو بناء مطار دولي في كل بلدة دون إنشاء أي طريق، وتكون التكلفة الإجمالية $7\times4=28$.

يمكن للشركة الثانية بناء 3 مطارات دولية على الأكثر بتكلفة $10$ لكل مطار. في هذه الحالة، من الحلول المثلى مثلًا إنشاء طريق بطول $9$ بين البلدتين $2$ و$4$ وآخر بطول $9$ بين البلدتين $3$ و$4$، وبناء مطارين دوليين في البلدتين $1$ و$2$. تكون التكلفة الإجمالية $10\times2+9+9=38$.

يمكن للشركة الثالثة بناء مطار دولي واحد على الأكثر بتكلفة $1$، لكن لا يمكن إنشاء طريق بين البلدة $1$ وأي بلدة أخرى، لذا يتطلب تحقيق شروط المسألة بناء مطارين دوليين على الأقل. لذلك لا تستطيع هذه الشركة تنفيذ المشروع، ونطبع -1.