Inženjer Zlatko dobio je zadatak provjeriti koliko je prijevoz učenika do škole busevima kvalitetan. U 2D-koordinatnom sustavu nalazi se \(N\) učenika s koordinatama \(u_x\) i \(u_y\) , te \(M\) autobusnih stanica s koordinatama \(s_x\) i \(s_y\). Na početku, na nekom polju može se nalaziti ili samo jedan učenik ili samo jedna stanica ili je to polje prazno.

Također, Inženjer Zlatko posjeduje popis \(K\) autobusnih linija: za svaku liniju ima listu stanica koju autobus na toj liniji obilazi redoslijedom kojim su stanice navedene. Jedna stanica nalazi se isključivo na jednoj liniji. Unutar jedne linije stanice se ne ponavljaju. Na jednoj liniji samo je jedan autobus. Dodatno, u svaki autobus stane najviše \(C\) učenika. Stanice nemaju ograničenje na broj učenika koji u njoj mogu čekati bus.

Kada jedan učenik uđe u autobus, on ne izlazi iz njega skroz do kraja vožnje dok autobus ne obiđe sve stanice na svojoj liniji. Učenik može ući u samo jedan autobus. Da bi učenik ušao u autobus, on mora doći do neke stanice koja se nalazi na nekoj od linija. Tada se duljina puta koju je učenik prehodao od svoje pozicije do stanice mjeri pomoću kvadrata euklidske udaljenosti: \((u_x - s_x)^2 + (u_y - s_y)^2\).

Inženjer Zlatko za svakog učenika odabire na koju će stanicu taj učenik ići te ih želi rasporediti tako da svi stanu u buseve poštujući zadana ograničenja. Slabost takvog rasporeda on mjeri u duljini puta koju mora prehodati učenik koji će najviše hodati.

Pomozite Inženjeru Zlatku i izračunajte najmanju moguću slabost puta i raspored učenika.

Ulazni​ podaci

U prvom retku nalaze se prirodni brojevi \(N\), \(M\), \(C\), \(K\) \((1 \leq N, M, C, K \leq 300 )\) iz teksta zadatka.

U sljedećih \(N\) redaka nalaze se cijeli brojevi \(u_x\) i \(u_y\) \((-1000 \leq u_x, u_y \leq 1000)\), koordinate pojedinog učenika.

U sljedećih \(M\) redaka nalaze se cijeli brojevi \(s_x\) i \(s_y\) \((-1000 \leq s_x, s_y \leq 1000)\), koordinate pojedine stanice.

U sljedećih \(K\) redaka nalaze se popisi stanica: prvo broj stanica \(K_i\) na toj liniji, a potom \(K_i\) brojeva \(st_j\) \(( 1 \leq st_j \leq M )\) koji označavaju stanice.

Izlazni podaci

Ako je raspoređivanje učenika poštujući ograničenja moguće, u prvi redak ispišite traženu slabost, a u sljedećih \(N\) redaka u \(i\)-tom retku ispišite stanicu na koju je raspoređen \(i\)-ti učenik. U slučaju da raspoređivanje na stanice s izračunatom slabošću nije jednoznačno, ispišite bilo koje raspoređivanje s takvom slabošću. Ako je raspoređivanje nemoguće, u jedini redak ispišite ‘\(-1\)’ (bez navodnika).

Bodovanje

U test podacima ukupno vrijednima \(50 \%\) bodova vrijedit će ograničenja: \(1 \leq N, M, K \leq 300, C = 1\).

U test podacima ukupno vrijednima \(30 \%\) bodova vrijedit će ograničenja: \(1 \leq N, M, K \leq 100, C \leq 10\).

Primjeri test​ podataka

Ulaz

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

Izlaz

4
1
1

Objašnjenje

Udaljenost koju oba učenika moraju prijeći do jedine stanice iznosi \(2\), a kvadrat te udaljenosti iznosi \(4\).

Ulaz

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

Izlaz

-1

Objašnjenje

Budući da postoji samo jedna linija, ukupno postoji samo jedan bus čiji kapacitet iznosi \(1\) što nije dovoljno da primi oba učenika.

Ulaz

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

Izlaz

9
1
1
3

Objašnjenje

Prva dva učenika idu na prvu stanicu. Najbliža stanica trećem učeniku je druga stanica, ali on se nalazi na liniji čiji je bus već popunjen. Stoga, on mora na treću stanicu i kvadrat duljine njegovog puta je \(9\). Svaka druga raspodjela učenika rezultira gorim rješenjem.