Priglavci

Engineer Zlatko checks how well students get to school by bus. In a 2D coordinate system there are $N$ students, and student $i$ sits at $(u_x, u_y)$. There are $M$ bus stops, and stop $j$ sits at $(s_x, s_y)$. A field holds one student, or one stop, or nothing.

Zlatko also has a list of $K$ bus lines. For every line he has the stops the bus calls at, written in the order they are listed. A stop belongs to at most one bus line, and the stops within one line are distinct. Every line has exactly one bus, and one bus fits $C$ students. The number of students waiting at a stop is not limited.

A student who boards a bus stays on it until the ride ends, after the bus has called at every stop of the line. A student boards only one bus. To board, a student must reach a stop of one of the bus lines. The length of the path a student walks from their position to a bus stop is measured as the squared Euclidean distance $(u_x - s_x)^2 + (u_y - s_y)^2$.

Zlatko picks the boarding stop of every student and distributes them so that the buses fit everyone and the limits above hold. The weakness of a distribution is the length walked by the student farthest from their boarding stop.

Help Zlatko and compute the minimal possible weakness together with the distribution that reaches it.

The first line contains the integers $N$, $M$, $C$, $K$ ($1 \le N, M, C, K \le 100$).

Each of the next $N$ lines contains the coordinates $u_x$ and $u_y$ of a student ($-1000 \le u_x, u_y \le 1000$).

Each of the next $M$ lines contains the coordinates $s_x$ and $s_y$ of a stop ($-1000 \le s_x, s_y \le 1000$).

Each of the next $K$ lines contains the stop list of one bus line: first the number of stops $K_i$ of that line, then $K_i$ stop numbers $st_j$ ($1 \le K_i \le M$, $1 \le st_j \le M$).

A stop appears in at most one line. No bus calls at a stop that appears in no line, so nobody boards there. All student and stop coordinates are distinct.

If every student can be distributed within the requirements, print the minimal weakness on the first line. On each of the next $N$ lines print the number of the stop student $i$ walks to, in the order the students are given.

Several distributions can reach the minimal weakness. Print the one whose sequence of stop numbers, read from the first student to the last, is lexicographically smallest: make the number of the first student as small as possible, then the number of the second student as small as possible, and so on down to the last student.

If no valid distribution exists, print -1.

In the first example both students walk a distance of 2 to the stop, and the square of that is 4.

In the second example there is a single line, so a single bus with a capacity of 1, which is not enough for two students.

In the third example two students go to stop 1 first. The nearest stop to the third student is stop 2, but the bus of the line that stop 2 belongs to is already full. The third student therefore goes to stop 3, and the square of that path length is 9. Every other distribution has a greater weakness.