学生选择最近检查点 - 曼哈顿距离算法

给定一个二维平面，上面有 N 个学生和 M 个检查点。第 i (1<=i<=n) 个学生的的位置在 (ai, bi)，第 j (1<=j<=m) 个检查点的 位置在 (cj, dj) 。

当老师给出信号后，每个学生都会跑向离他最近的检查点。在这里，我们用曼哈顿距离来定义学生距离与检查点的距离。 曼哈顿距离的定义是：点 (x1,y1) 和 (x2,y2) 的曼哈顿距离等于 |x1−x2|+|y1−y2|。其中，|x| 表示 x 的绝对值。

如果有多个检查点离某个学生距离相等，他/她会选择编号最小的那个。请聪明的你算算，每个学生分别会选择跑向哪个检查点。

输入格式: 第一行包含两个整数 N 和 M，表示学生的数量和检查点的数量。 接下来 N 行，每行包含两个整数 ai 和 bi，表示第 i 个学生的位置。 接下来 M 行，每行包含两个整数 cj 和 dj，表示第 j 个检查点的位置。

输出格式: 输出 N 行，每行包含一个整数，表示每个学生选择的检查点的编号。

输入样例: 5 4 1 1 2 2 3 3 4 4 5 5 1 3 2 1 3 4 4 2

输出样例: 2 1 3 4 4