题目描述

两组穴居人发生了土地纠纷，决定用老办法解决——互相扔棍子。争斗是在一个山洞里发生的，这个山洞很高，所以不用担心棍子飞得太高，但是地面上的矿藏却会妨碍棍子的飞行。

洞可以划分为 $r$ 行和 $c$ 列，所以整个洞口由 $r \times c$ 个单元格组成（可当作一个竖直的平面）。

洞穴中的每一个单元格要么是空的，要么含有一块矿物块。如果两块矿物块在四个主要方向（上、下、左、右）中的一个方向上相邻，则判定它们属于同一矿群。

争斗开始时，一组穴居人在山洞的左侧，另一组穴居人则在右侧。这两组人轮流向另一组人投掷棍子，先由一组人选择棍子飞行的高度，然后（必要时爬到别人的肩膀上）投掷，棍子将在选定的高度上水平飞过洞穴。

如果棍子在路上撞到了一块矿物块，该单元格处的矿物块将被击碎（即不复存在），棍子也将同时掉落至地面而停止飞行。

当一个矿物块被击碎后，与其相连的矿物块群可能因不再有矿物块与其相连作为支撑物而因重力向地面坠落。在下落的过程中，矿物块群不会改变形状，即其中所有的矿物块将会一起下落。如果下落时某个矿物块落在地面上，整个矿物块群就会停止下落并成为一个新产生的矿物块。特别地，如果一个矿物块落在另一个矿物块上，它们就会合并成为一个矿物块。

现在已知洞穴中矿物块的布局和扔棍子的高度，请确定这场争斗结束后，洞内的矿物布局。

输入格式

第一行，两个整数 $r$, $c$，含义见题目描述。

接下来是一个字符表，共有 $r$ 行 $c$ 列。其中，. 代表一个空单元格，x 代表一个含有矿物块的单元格。

接下来一行，一个正整数 $n$，表示木棍数。

最后一行，$n$ 个整数，表示棍棒的投掷高度。高度 $1$ 为矩阵的底部，高度 $r$ 为顶部。 第一根棍将从左向右飞行，第二根则从右向左飞行，以此类推。

输出格式

共 $r$ 行，每行 $c$ 个字符，表示洞穴的最终布局。

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3 

......
......
..xx..
..xx..
.xxxx. 

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1 

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx. 

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4 

......
......
......
......
..xx..
xx.xx.
.x..x. 

提示

样例 #2 解释

第一根木棍将第 $4$ 列高度为 $6$ 的矿物块击碎，未使任何矿物块失去支撑而下落；

第二根木棍将第 $7$ 列高度为 $6$ 的矿物块击碎，未使任何矿物块失去支撑而下落；

第三根木棍将第 $3$ 列高度为 $4$ 的矿物块击碎，使第 $4$ 列高度为 $4$ 和 $5$ 的两个矿物块下落直至与该列高度为 $1$ 的矿物块合并；

第四根木棍将第 $7$ 列高度为 $3$ 的矿物块击碎，使第 $6$ 列高度为 $3$ 的矿物块连带着第 $5$ 列高度为 $3$，$4$，$5$ 的矿物块以及第 $6$ 列高度为 $6$ 的矿物块一起下落直至落至地面；

第五根木棍将第 $2$ 列高度为 $1$ 的矿物块击碎，未使任何矿物块失去支撑而下落。

数据规模及约定

• 对于 $100\%$ 的数据，$1\le r,c,n \le 100$。
• 对于 $100\%$ 的数据，保证初始状态下不会有任何一个碎块群漂浮在空中，且在任何时间点都不会有两个或两个以上的碎块群同时落下。

说明

• 本题满分 $120$ 分。
• 本题译自 COCI2008-2009 CRCI2008-2009 RELJEF，
  https://www.luogu.com.cn/user/219791