题目描述

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 ux and uy, and M bus stops with coordinates sx and sy. 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: (ux - sx)2 + (uy - sy)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.

题目翻译

工程师 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 并计算最小可能的弱点和学生的分布。

INPUT

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

Each of the following N lines contains integers $u_x$ and $u_y$ (-1000 ≤ ux, uy ≤ 1000), the students’ coordinates.

Each of the following M lines contains integers $s_x$ and $s_y$ (-1000 ≤ sx, sy ≤ 1000), the stops’ coordinates.

Each of the following K lines contains the list of bus stops: first, the number of stops Ki of the bus line, then Ki numbers stj (1 ≤ stj ≤ M) that denote the stops.

OUTPUT

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 ith line must contain the stop the ith 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’ (without quotes).

样例 #1

样例输入 #1

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

样例输出 #1

4
1
1

样例 #2

样例输入 #2

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

样例输出 #2

-1

样例 #3

样例输入 #3

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

样例输出 #3

9
1
1
3

SCORING

In test cases worth 50% of total points, it will hold C = 1.

In test cases worth additional 30% of total points, it will hold 1 ≤ C ≤ 10.

提示

Clarification of the first test case:

两个学生必须步行到公共汽车站的距离为 2。该实例的平方值为 4。

Clarification of the second test case:

由于只有一条线路，因此总共只有一辆载客量为 1 的公交车，不足以合理分配所有学生。

Clarification of the third test case:

首先，两个学生去第一站。 离第三个学生最近的站是第二站，但该站属于已经满员的公交线路。 因此，第三个学生必须去第三站，他们的路径长度的平方值为9。每隔一个分布导致更大的弱点。