במדינת 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$ המופרדים ברווחים. הם מציינים שהפינה השמאלית התחתונה של המלבן המייצג את האזור האסור ה־$j$ היא $(P_j,Q_j)$, והפינה הימנית העליונה היא $(R_j,S_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$ מבצעת את הפרויקט. אם החברה ה־$k$ אינה יכולה לבצע את הפרויקט בהתאם לתנאים, הדפיסו במקום זאת את המספר השלם $-1$.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $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$).
• אין שתי עיירות או יותר באותן קואורדינטות.
• $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$).
• אף אזור אינו מכיל עיירה בתוך המלבן שלו או על שפתו.
• $1\le B_k\le1\,000\,000\,000$ ($1\le k\le C$).
• $1\le H_k\le N$ ($1\le k\le C$).

תתי־משימות

תת־משימה 1 [10 נקודות]

מתקיימים התנאים הבאים.

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

תת־משימה 2 [30 נקודות]

מתקיימים התנאים הבאים.

• $C\le100$.

תת־משימה 3 [30 נקודות]

מתקיימים התנאים הבאים.

• $M\le100$.

תת־משימה 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$ ואת עיירות $3$ ו־$4$, ולבנות נמלי תעופה בעיירות $1$ ו־$2$. העלות הכוללת היא $10\times2+9+9=38$.

החברה השלישית יכולה לבנות לכל היותר נמל תעופה בינלאומי אחד בעלות 1. אולם מאחר שאי אפשר לסלול כביש בין עיירה $1$ לאף עיירה אחרת, יש לבנות לפחות שני נמלי תעופה בינלאומיים כדי לעמוד בתנאי הבעיה. לכן חברה זו אינה יכולה לבצע את הפרויקט, ומדפיסים -1.