Description

你说得对，但是**《脑叶公司》** 是由划记亮月 自主研发的一款策略模拟游戏。游戏的灵感来源于在小说、游戏和电影中登场的怪物们，例如《PCS基金会》，《屋中小林》，《第114514号仓库》等等。故事发生在「后巷、城区、巢」的世界，你将被授予「A」的头衔，扮演一位怪物管理公司的主管，不断解锁新的部门，研发新的科技，遇见形形色色的怪诞生物，引导融毁之力，邂逅核心抑制，和白夜、终末相亲相爱，同时，寻找「轮回」的真相。​

如果发生异想体脱离收容的情况，那我们就不得不严肃考虑如何处理主管了。

你是一位打折入手新上任的主管，可是霉运当头的你，即将遇到有史以来最为严重的逆卡巴拉能量融毁 ;
**
**
为了防止异想体计数器归零导致的逃离收容，你需要知道到达各个收容室的最少 时间，以此能最高效率地安排你的员工处理融毁。

可是你同时在处理的mememe核心抑制 会影响你的行进方向，让你只能按照给定的限制移动。

你能解决这次逆卡巴拉能量融毁 保护好你的员工吗？（

马猴烧酒镇题

————————————————————————————————

换句话说：

给定一个 $n \times m$ 的脑叶本部地图，地图上存在障碍物，任何时候都不能移动到障碍物上；

给定一个起点坐标 $(bx, by)$；

给定$k$ 个由于 mememe核心限制 产生的移动限制，主管的一次移动方式只能为给定的其中一个限制。

例如 ：给定 $（-1，0）$限制，下一步能走到上方第一个格子，给定 $（0，1）$限制，下一步能走到右方第一个格子，给定$（2，0）$限制，下一步能走到下方第二个格子 （目的地不能离开地图或者是障碍物），移动是瞬移的，不会在中途被障碍物阻挡。

问到达每一个异想体收容室的最少时间，如果无法到达或者该位置为障碍物，输出字符串 $"inf"$（不包含引号）

特别的，如果主管 “有幸” 初始就在障碍物中，默认主管在安全的 “3月27号的避难所 ”，该障碍物视为一个收容室，但之后主管将不能再进行任何移动（三级预警 ! ! !）

Format

Input

输入两个数字 $n$，$m$，表示地图的大小 。

接下来 $n$ 行，每行长度为 $m$ 的 $01$ 字符串，$0$表示障碍物，$1$表示收容室，地图左上角坐标为$（1，1）$，右下角坐标为$（n，m）$。

然后再输入两个数字 $bx， by$，表示起点的坐标（保证在地图内）。

最后输入一个 $k$，之后 $k$ 行每行一个两元组 $（x, y）$，表示移动限制。

$1 \leq n,m \leq 50$

$0 \leq k \leq 100000$

$-1e9 \leq x,y \leq 1e9$

Output

输出 $n$ 行，每行 $m$ 个输出由空格隔开（注意行末无空格）

如果该处能抵达输出最少的移动次数，否则输出字符串 $"inf"$ （不包含引号）

Samples

3 3
101
101
101
2 2
0

inf inf inf
inf 0 inf
inf inf inf

1 10
1111110111
1 1
1
0 1

0 1 2 3 4 5 inf inf inf inf

3 3
111
111
111
2 2
2
1 1
-1 -1

1 inf inf
inf 0 inf
inf inf 1

Hint