Engineer Zlatko got assigned the task of checking the quality of transportation for students getting to school by bus. In a 2D-coordinate system, there are $N$ students with coordinates $u_x$ and $u_y$, and $M$ bus stops with coordinates $s_x$ and $s_y$. At the beginning, a field can be occupied by one student or by one stop, or it can be empty.

Also, engineer Zlatko has a list of $K$ bus lines: for each bus line, he has a list of stops the bus stops at in the order in which the stops are listed. One stop belongs exclusively to one bus line. The stops are distinct within a bus line. There is only one bus per line. Additionally, each bus can fit $C$ students. Bus stops don't have a limit on the number of students that could be waiting for it.

When a student boards a bus, they don't get off until the end of the ride when the bus has stopped at all stops of the line. A student can board only one bus. For a student to board a bus, they must reach a stop of one of the bus lines. The length of the path which a student walked from their position to a bus stop is measured as the squared Euclidean distance: $(u_x-s_x{)}^2+(u_y-s_y{)}^2$.

Engineer Zlatko chooses the boarding stop for each student and distributes them so that the buses can fit everyone, respecting the given limitations. The weakness of the distribution of students is measured as the distance walked by the student farthest from their boarding bus stop.

Help engineer Zlatko and calculate the minimal possible weakness and the distribution of students.

Input Specification

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

Each of the following $N$ lines contains integers $u_x$ and $u_y$ $(-1000\le u_x,u_y\le 1000)$, the students' coordinates.

Each of the following $M$ lines contains integers $s_x$ and $s_y$ $(-1000\le s_x,s_y\le 1000)$, the stops' coordinates.

Each of the following $K$ lines contains the list of bus stops: first, the number of stops $K_i$ of the bus line, then $K_i$ numbers $s{t}_j$ $(1\le s{t}_j\le M)$ that denote the stops.

Output Specification

If it is possible to distribute the students within the requirements, you must output the required weakness in the first line, and in the following $N$ lines, the $i^{\text{th}}$ line must contain the stop the $i^{\text{th}}$ student must walk to. In the case that the distribution of students to bus stops with the calculated weakness is not unique, output an arbitrary distribution with such weakness.

If it is impossible to distribute the students, you must output -1.

Scoring

In test cases worth $50\mathrm{\%}$ of total points, it will hold $C=1$.

In test cases worth additional $30\mathrm{\%}$ of total points, it will hold $1\le C\le 10$.

Sample Input 1

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

Sample Output 1

4
1
1

Explanation for Sample Output 1

The distance which both students must walk to a bus stop is 2. The squared value of that instance is 4.

Sample Input 2

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

Sample Output 2

-1

Explanation for Sample Output 2

Since only one line exists, in total there is a single bus with a capacity of 1, which is not sufficient to distribute all the students properly.

Sample Input 3

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

Sample Output 3

9
1
1
3

Explanation for Sample Output 3

Firstly, two students go to the first stop. The nearest stop to the third student is the second stop, but that stop belongs to the bus line of an already full bus. Therefore, the third student must go to the third stop, and the squared value of their path length is 9. Every other distribution results in greater weakness.