Priglavci

Στον μηχανικό Zlatko ανατέθηκε το καθήκον να ελέγχει την ποιότητα της μεταφοράς των μαθητών που φτάνουν στο σχολείο με λεωφορείο. Σε ένα σύστημα δισδιάστατων συντεταγμένων, υπάρχουν ~N~ μαθητές με συντεταγμένες ~u_x~ και ~u_y~, και ~M~ στάσεις λεωφορείων με συντεταγμένες ~s_x~ και ~s_y~. Στην αρχή, ένα πεδίο μπορεί να καταλαμβάνεται από έναν μαθητή ή από μία στάση, ή μπορεί να είναι άδειο.

Επίσης, ο μηχανικός Zlatko έχει μια λίστα με γραμμές ~K~ λεωφορείων: για κάθε γραμμή λεωφορείου, έχει μια λίστα με στάσεις στις οποίες σταματά το λεωφορείο με τη σειρά με την οποία αναφέρονται οι στάσεις. Μία στάση ανήκει αποκλειστικά σε μία λεωφορειακή γραμμή. Οι στάσεις είναι ευδιάκριτες μέσα σε μια γραμμή λεωφορείου. Υπάρχει μόνο ένα λεωφορείο ανά γραμμή. Επιπλέον, κάθε λεωφορείο μπορεί να χωρέσει ~C~ μαθητές. Οι στάσεις λεωφορείων δεν έχουν όριο στον αριθμό των μαθητών που θα μπορούσαν να περιμένουν σε αυτές.

Όταν ένας μαθητής επιβιβάζεται σε λεωφορείο, δεν κατεβαίνει μέχρι το τέλος της διαδρομής, αφού το λεωφορείο έχει σταματήσει σε όλες τις στάσεις της γραμμής. Ένας μαθητής μπορεί να επιβιβαστεί μόνο σε ένα λεωφορείο. Για να επιβιβαστεί ένας μαθητής σε λεωφορείο, πρέπει να φτάσει σε μια στάση μιας από τις γραμμές του λεωφορείου. Το μήκος του μονοπατιού που περπάτησε ένας μαθητής από τη θέση του μέχρι τη στάση του λεωφορείου μετριέται ως η τετράγωνη Ευκλείδεια απόσταση: ~(u_x - s_x^2) + (u_y - s_y^2)~

Ο μηχανικός Zlatko επιλέγει τη στάση επιβίβασης για κάθε μαθητή και την κατανέμει έτσι ώστε τα λεωφορεία να τους χωρούν όλους, σεβόμενοι τους δεδομένους περιορισμούς. Η αδυναμία της κατανομής των μαθητών μετριέται ως η απόσταση που έχει διανύσει ο μαθητής πιο μακριά από τη στάση του λεωφορείου επιβίβασής του.

Βοηθήστε τον μηχανικό Zlatko και υπολογίστε την ελάχιστη δυνατή αδυναμία και την κατανομή των μαθητών.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N,\;M,\;C,\;K\;(1 \le N, M, C, K \le 100)~ από την εργασία.
Κάθε μία από τις ακόλουθες γραμμές ~N~ περιέχει ακέραιους αριθμούς ~u_x~ και ~u_x\;(-1\,000 \le u_x,\;u_y \le 1\,000)~, τις συντεταγμένες των μαθητών.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει ακέραιους αριθμούς ~x~ και ~s_y\;(-1\,000 \le s_x,\;s_y \le 1\,000)~, τις συντεταγμένες των στάσεων.
Καθεμία από τις ακόλουθες ~K~ γραμμές περιέχει τη λίστα των στάσεων λεωφορείων: πρώτα, ο αριθμός των στάσεων ~K_i~ της γραμμής λεωφορείου, μετά ~K_i~ αριθμοί ~st_j\;(1 \le st_j \le M)~ που δηλώνουν τις στάσεις.

Έξοδος

Εάν είναι δυνατό να κατανεμηθούν οι μαθητές εντός των απαιτήσεων, πρέπει να τυπώσετε την απαιτούμενη αδυναμία στην πρώτη γραμμή και στις ακόλουθες ~N~ γραμμές, κάθε ~i~-οστή γραμμή πρέπει να περιέχει την ~i~-οστή στάση στην οποία πρέπει να περπατήσει ο μαθητής. Στην περίπτωση που η κατανομή των μαθητών σε στάσεις λεωφορείων με την υπολογισμένη αδυναμία δεν είναι μοναδική, τυπώστε μια αυθαίρετη κατανομή με τέτοια αδυναμία. Εάν είναι αδύνατη η διανομή των μαθητών, πρέπει να τυπώσετε "-1" (χωρίς εισαγωγικά).

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 50% των συνολικών πόντων, θα ισχύει ~C = 1~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 30% των συνολικών πόντων, θα ισχύει ~1 \le C \le 10~.

Παραδείγματα

input

2 1 2 1
2 1
2 5
2 3
1 1

output

4
1
1

Επεξήγηση του 1ου παραδείγματος:

Η απόσταση που πρέπει να περπατήσουν και οι δύο μαθητές μέχρι μια στάση λεωφορείου είναι 2. Η τετραγωνική τιμή αυτής της περίπτωσης είναι 4.

input

2 1 1 1
2 1
2 5
2 3
1 1

output

-1

Επεξήγηση του 2ου παραδείγματος:

Δεδομένου ότι υπάρχει μόνο μία γραμμή, συνολικά υπάρχει ένα μόνο λεωφορείο χωρητικότητας 1, το οποίο δεν επαρκεί για τη σωστή κατανομή όλων των μαθητών.

input

3 3 2 2
1 3
2 2
8 7
3 4
6 7
8 4
2 1 2
1 3

output

9
1
1
3

Επεξήγηση του 3ου παραδείγματος:

Αρχικά, δύο μαθητές πηγαίνουν στην πρώτη στάση. Η πλησιέστερη στάση στον τρίτο μαθητή είναι η δεύτερη στάση, αλλά αυτή ανήκει στη γραμμή ενός ήδη γεμάτου λεωφορείου. Επομένως, ο τρίτος μαθητής πρέπει να πάει στην τρίτη στάση και η τετραγωνική τιμή του μήκους της διαδρομής του είναι 9. Κάθε άλλη κατανομή έχει ως αποτέλεσμα μεγαλύτερη αδυναμία