工程师 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 为每个学生选择乘车的车站，并对他们进行分配，使得公交车能够容纳所有人，且满足给定的限制条件。学生分配方案的代价（weakness）定义为所有学生中步行到其乘车站点的最大距离（平方）。

请帮助工程师 Zlatko 计算最小的可能代价以及学生的分配方案。

输入格式

输入的第一行包含四个整数 $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$，然后是 $K_i$ 个整数 $st_j$ ($1 \le st_j \le M$)，表示这些车站的编号（按 $1$ 到 $M$ 编号）。

输出格式

如果可以满足要求分配学生，请在第一行输出最小的代价。

在接下来的 $N$ 行中，第 $i$ 行应包含第 $i$ 个学生必须步行前往的车站编号。如果存在多种使代价最小的分配方案，输出其中任意一种即可。

如果无法分配学生，请输出 -1。

子任务

• 在占总分 $50\%$ 的测试数据中，满足 $C = 1$。
• 在另占总分 $30\%$ 的测试数据中，满足 $1 \le C \le 10$。

样例

输入 1

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

输出 1

4
1
1

输入 2

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

输出 2

-1

输入 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

说明

样例 1 说明： 两个学生步行到车站的距离均为 $2$。该距离的平方值为 $4$。

样例 2 说明： 由于只有一条公交线路，总共只有一辆容量为 $1$ 的公交车，这不足以容纳所有的学生。

样例 3 说明： 首先，前两个学生前往第 $1$ 个车站。距离第 $3$ 个学生最近的车站是第 $2$ 个车站，但该车站属于一辆已经满载的公交线路。因此，第 $3$ 个学生必须前往第 $3$ 个车站，其步行路径长度的平方值为 $9$。任何其他分配方案都会导致更大的代价。