Priglavci

엔지니어 즐라트코는 학생들이 버스로 등교하는 환경이 얼마나 좋은지 점검한다. 2차원 좌표평면에 학생 $N$명이 있고 $i$번째 학생의 좌표는 $(u_x, u_y)$다. 버스 정류장은 $M$개가 있고 $j$번째 정류장의 좌표는 $(s_x, s_y)$다. 한 칸에는 학생 한 명 또는 정류장 하나만 있거나, 아무것도 없다.

즐라트코는 버스 노선 $K$개의 목록도 받았다. 노선마다 버스가 정차하는 정류장이 나열된 순서대로 적혀 있다. 한 정류장은 많아야 한 노선에만 속하고, 한 노선 안에서 정류장 번호는 서로 다르다. 노선마다 버스는 한 대씩 있고, 버스 한 대에는 학생 $C$명까지 탈 수 있다. 정류장에서 버스를 기다리는 학생 수에는 제한이 없다.

버스에 탄 학생은 그 노선의 모든 정류장을 도는 운행이 끝날 때까지 내리지 않는다. 학생 한 명은 버스 한 대에만 탄다. 버스에 타려면 학생은 어떤 노선의 정류장까지 걸어가야 한다. 학생이 자기 위치에서 정류장까지 걸어간 경로의 길이는 유클리드 거리의 제곱 $(u_x - s_x)^2 + (u_y - s_y)^2$으로 잰다.

즐라트코는 학생마다 탑승할 정류장을 정해서, 주어진 제한을 지키면서 모든 학생이 버스에 타도록 배치한다. 배치의 취약도는 자기 탑승 정류장에서 가장 멀리 떨어진 학생이 걸은 길이로 정의한다.

즐라트코를 도와 가능한 최소 취약도와 그때의 배치를 구하라.

첫째 줄에 정수 $N$, $M$, $C$, $K$가 주어진다 ($1 \le N, M, C, K \le 100$).

다음 $N$개 줄에 학생의 좌표 $u_x$와 $u_y$가 주어진다 ($-1000 \le u_x, u_y \le 1000$).

다음 $M$개 줄에 정류장의 좌표 $s_x$와 $s_y$가 주어진다 ($-1000 \le s_x, s_y \le 1000$).

다음 $K$개 줄에 각 노선이 정차하는 정류장 목록이 주어진다. 먼저 그 노선의 정류장 수 $K_i$가 나오고, 이어서 정류장 번호 $st_j$가 $K_i$개 주어진다 ($1 \le K_i \le M$, $1 \le st_j \le M$).

한 정류장은 많아야 한 노선에만 나온다. 어느 노선에도 나오지 않는 정류장에는 버스가 서지 않으므로 그 정류장에서는 아무도 탈 수 없다. 학생과 정류장의 좌표는 모두 서로 다르다.

모든 학생을 조건에 맞게 배치할 수 있으면 첫째 줄에 최소 취약도를 출력한다. 이어지는 $N$개 줄에는 $i$번째 학생이 걸어갈 정류장의 번호를 학생이 입력된 순서대로 출력한다.

최소 취약도를 만드는 배치가 여럿이면 출력할 정류장 번호를 위에서부터 늘어놓은 수열이 사전순으로 가장 앞서는 배치를 출력한다. 즉 첫 번째 학생의 번호를 가장 작게 하고, 그 조건에서 두 번째 학생의 번호를 가장 작게 하고, 이런 식으로 마지막 학생까지 정한다.

배치가 불가능하면 -1을 출력한다.

첫 번째 예제에서 두 학생이 정류장까지 걸어야 하는 거리는 2이고, 그 제곱은 4다.

두 번째 예제에는 노선이 하나뿐이라 버스도 한 대뿐인데 정원이 1명이므로 학생 두 명을 모두 태울 수 없다.

세 번째 예제에서는 먼저 두 학생이 1번 정류장으로 간다. 세 번째 학생에게 가장 가까운 정류장은 2번이지만, 2번 정류장이 속한 노선의 버스는 이미 가득 찼다. 따라서 세 번째 학생은 3번 정류장으로 가고, 걸은 길이의 제곱은 9다. 다른 배치는 모두 취약도가 더 크다.