多源洪水填充

给定一个 N 行 M 列的网格，每个格子是 '0'（墙壁）或 '1'（空地）。

给定 K 个水源点，每一秒水从每个水源点同时向四周扩散到相邻空地（上下左右四个方向）。求每个空地格子第一次被水到达的时间（即距离最近水源的曼哈顿步数）。

对于墙壁格子，输出 -1；对于水源点，输出 0；对于其他空地格子，输出被水到达的时间。

输入格式

第一行三个整数 N, M, K。 接下来 N 行，每行 M 个字符（'0' 或 '1'），表示网格。 接下来 K 行，每行两个整数 r, c，表示水源点的坐标（行号和列号均为 1-indexed）。 保证水源点坐标对应的格子一定是 '1'。

输出格式

输出 N 行，每行 M 个整数，表示每个格子的结果。整数之间用空格分隔。

样例

3 3 1
111
111
111
2 2

1 1 1
1 0 1
1 1 1

限制

1 ≤ N, M ≤ 500 1 ≤ K ≤ 10 时间限制：1.0 秒 空间限制：256 MB