1503: 袋鼠跳跃

在无限大的平面直角坐标系上有 $n$ 个袋鼠部落。

袋鼠部落的领地都可以看作一个矩形，其中第 $i$ 号部落领地的左下角坐标为 $(x_i,y_i)$ ，长为 $a_i$ ，宽为 $b_i$ ，这意味着第 $i$ 个部落领地的右上角坐标为 $(x_i+a_i,y_i+b_i)$。第 $i$ 号部落的领地的 每个整数点 上都有一只属于第 $i$ 号部落的袋鼠。第 $i$ 号部落的袋鼠的极限跳跃距离是 $k_i$ 。

袋鼠是一种跳着走的同时 不会转身 的生物。我们认为上和下相对，左和右相对。第 $i$ 号部落的袋鼠跳跃可以从$上，下，左 , 右，左上，左下，右上，右下$ 这 $8$ 个方向选择一个，并选择跳跃 $z$ 的距离。
具体来说，对于位于 $(e,f)$ 的袋鼠跳跃一次后:  
1.它可以移动到 $(e,f+z)$  
2.它可以移动到 $(e,f-z)$  
3.它可以移动到 $(e-z,f)$  
4.它可以移动到 $(e+z,f)$   
5.它可以移动到 $(e-z,f+z)$  
6.它可以移动到 $(e-z,f-z)$  
7.它可以移动到 $(e+z,f+z)$  
8.它可以移动到 $(e+z,f-z)$   
其中$1 \le z \le k_i$ ,且 $z$ 是整数。不要求 每次跳跃时选的 $z$ 一致。

注意： 袋鼠不会转身 ，所以当选择了某个方向跳跃后，之后选定的方向不能带有与之前相对的方向。例如：之前向左跳跃过，由于左和右相对，则之后都不能选择向右，右上，右下跳跃。  

袋鼠部落之间用信件交流。当部落 $c$ 向 部落 $d$ 送信件时，部落 $c$ 会在部落内 选出一只袋鼠 作为信使，当信使位于的点上存在属于部落 $d$ 的袋鼠时视为完成送信。

现在，袋鼠们想要知道当部落间送信时，信使需要跳跃的最小次数。  

为此，你需要输出一个 $n*n$ 的矩阵，第 $i$ 行 $j$ 列上的数代表第 $i$ 号部落向第 $j$ 号部落送信时，信使需要跳跃的最小次数。

第一行，一个整数 $n$。代表袋鼠部落的数量。  
接下来 $n$ 行，每行 $5$ 个整数。第 $i$ 行的整数依次代表 $x_i$ , $y_i$ , $a_i$ , $b_i$ , $k_i$。（含义见上文） 


数据范围:   
$1 \le n \le 1000$  
$-10^9 \le x_i,y_i \le 10^9$  
$0 \le a_i,b_i \le 10^9$  
$1 \le k_i \le 10^9$  

$n$ 行，每行 $n$ 个整数。  
第 $i$ 行 $j$ 列上的数代表第 $i$ 号部落向第 $j$ 号部落送信时，信使需要跳跃的最小次数。

4
0 0 5 5 2
-10 5 6 6 3
1 1 2 2 4
10 10 10 10 10

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