时间限制： 4.0 秒

空间限制： 512 MB

题目描述

《绝地求生》是一款战术竞技型射击类沙盒游戏，玩家需要在游戏地图上收集各种资源，并在不断缩小的安全区域内对抗其他玩家，让自己生存到最后。

本题简化了游戏规则，需要你计算出最终的游戏结果，简化版规则如下。

游戏规则

游戏地图是 $n \times n$ 的正方形棋盘，由 $1 \times 1$ 的方格组成，每个玩家用一个 $1 \times 1$ 的方格表示。

在不超出棋盘边界的情况下，玩家可以向八个方向（上、下、左、右、左上、左下，右上、右下）移动，进入周围的格子，一次移动称为一步。下图示意性地给出了玩家 a 和玩家 b 可能的移动方向，由于玩家 b 位于棋盘的边缘，因此可能的移动方向仅有 5 种。

棋盘中可能有障碍物，障碍物也是 $1 \times 1$ 的方格，玩家不能进入障碍物的方格，也不能穿越两个斜向相邻障碍物方格的间隙。

不同玩家之间互不影响，他们可以出现在一个方格里面。

游戏流程

游戏开始时，会给出棋盘的大小、玩家数量、障碍物数量、每个障碍物的位置、每个玩家的初始位置。所有的玩家在游戏开始时，都会被赋予相等的“生命值”。一次游戏分为多个回合，在游戏开始时，会给出本次游戏的回合数目。

每回合开始时，都会给出每个玩家的目标位置。在这一回合内，玩家需要从上一回合结束时的位置（对于第一回合则为初始位置）移动到这一回合的目标位置，移动的步数不限。如果玩家在这一回合的起始位置和某一障碍物重合，那么假定在这一回合内，该障碍物对于该玩家是失效的。

下图中给出了某一回合开始时，玩家 a 的位置 $(1,2)$ 和目标位置 $(1,3)$，以及玩家 b 的位置 $(2,0)$ 和目标位置 $(3,3)$。

每一回合内，都会出现大小、位置都固定不变的一个圆形的安全区域，直到本回合结束。安全区域的圆心位于方格中心，如果某个方格的中心到圆心的直线距离小于或等于安全区域的半径，那么这个方格就是安全的。从不安全的方格移动一步到其他位置会被扣除 1 点生命值。安全的方格内的障碍物将会在本回合失效，允许玩家通过。所有玩家的目标位置保证是安全的。

图中圆心的方格坐标是 $(2,3)$，半径为 $2$，浅灰色的方格是安全的方格，安全的方格内的障碍物会在本回合失效。

你的任务是，为每一位玩家找到生命值扣除最少的移动路线。若对于某位玩家，任何到达本回合目标位置的移动路线都会导致生命值扣除至 0，则称该玩家死亡。死亡的玩家不参与之后回合的游戏。

下图展示生命值扣除最少的移动路径，在此过程中，玩家 a 不被扣除生命值，玩家 b 被扣除 1 点生命值。

所有回合结束后，你需要输出所有玩家剩余的生命值，已经死亡的玩家输出 0。

输入格式

从标准输入读入数据。

输入第一行包括五个整数：$n,m,e,f,h$，表示棋盘为 $n \times n$ 大小，一共有 $m$ 个玩家，棋盘上有 $e$ 个障碍物，游戏一共有 $f$ 个回合，玩家的初始生命值是 $h$。保证 $1\le n\le 400,~1\le m\le 10^5,~0\le e\le n^2,~1\le f\le 10,~0<h\le 2.5n$。

接下来有 $e$ 行，每行包含两个整数 $p,q$，$(p,q)$ 即为该障碍物所在方格的坐标，其中 $0 \leq p,q < n$。

随后有 $m$ 行，每行包含两个整数 $i,j$，$(i,j)$ 即为该玩家初始所在方格的坐标，其中 $0 \leq i,j < n$。

随后有 $f$ 个回合的数据，每个回合的数据有 $m+1$ 行。其中，包含一行安全区信息以及 $m$ 行玩家移动目标。安全区信息包括三个整数，$a,b,r$，$(a,b)$ 表示安全区圆心所在方格的坐标，$r$ 表示安全区半径。玩家移动目标包含两个整数，$u$ 和 $v$，$(u,v)$ 表示玩家移动目标的方格坐标。即使玩家已经死亡，也会提供移动目标，但是并不需要进行计算。其中 $0 \leq a,b,u,v < n,~0 < r \leq 200$。保证每个玩家给出的目标坐标一定在安全区域以内。保证在任意回合，对于任意玩家，都存在一条到达本回合目标位置的移动路线。

所有输入都是整数。

输出格式

输出到标准输出。

输出 $m$ 行，每行包含一个整数：$z$，表示该玩家的最终生命值。

$m$ 个玩家的输出顺序与输入顺序相同。

4 2 4 1 1
0 3
1 1
2 2
3 0
1 2
2 0
2 3 2
1 3
3 3

1
0

子任务

共有四个子任务，每个子任务均包含一个或多个测试点。若你的程序对一个子任务的全部测试点，都能给出正确的输出，则得该子任务的满分，否则该子任务得 0 分。本题满分共计 100 分。

子任务 1（19 分）：输入数据保证无障碍物，每回合开始玩家都在安全区中；

子任务 2（23 分）：输入数据保证无障碍物，每回合开始玩家不一定在安全区中，$1\le n\le 10,~1\le m\le 20$；

子任务 3（17 分）：输入数据保证无障碍物，每回合开始玩家不一定在安全区中，$10<n\le 400,~20<m\le 10^5$；

子任务 4（25 分）：输入数据保证有障碍物，$1\le n\le 10,~1\le m\le 20$；

子任务 5（16 分）：输入数据保证有障碍物，$10<n\le 400,~20<m\le 10^5$。