作为《超级马威欧兄弟》（Super Mawio Bros）的关卡设计师，你一直在为马威欧（Mawio）设计游戏地图。每张地图都由空白区域、砖块和道具箱组合而成，马威欧需要在其中穿行以拯救普威琪公主（Princess Pweach）。为了让一些地图变得更有趣，你决定在地图中加入一些瀑布。当这些瀑布从屏幕顶部向下流淌时，它们会自然地绕过你已经放置好的砖块和道具箱。

目前，地图中只包含砖块、道具箱和空白区域。瀑布将被放置在屏幕顶部的某些特定列。根据这些信息，输出一张更新后的地图，其中显示出瀑布的路径。

水流会直接向下流，除非被砖块或道具箱阻挡。当水流被障碍物阻挡时，它会向该障碍物的左侧和右侧分流，除非这些位置也被阻挡。当水流流到地图底部时，它会在接触到最底层的位置停止流动。

在当前的地图表示中，空白区域用字符 O 表示，砖块用字符 # 表示，道具箱用字符 ? 表示。在更新后的表示中，水流应该用字符 ~ 表示。关卡的最顶层不会有任何砖块或道具箱。

输入格式

第一行包含三个空格分隔的整数 $n$，$m$ 和 $k$（$1 \le n, m \le 1000$，$1 \le k \le m$）。$n$ 和 $m$ 分别代表地图的行数和列数。$k$ 代表需要添加的瀑布数量。

第二行包含 $k$ 个空格分隔的整数，每个整数代表需要添加在地图顶部的瀑布的列位置 $p_k$（$0 \le p_k < m$）。

接下来的 $n$ 行，每行包含 $m$ 个字符。这 $n$ 行代表关卡的 $n \times m$ 地图。空白区域用字符 O 表示，砖块用字符 # 表示，道具箱用字符 ? 表示。

输出格式

输出 $n$ 行，每行包含 $m$ 个字符。这些行应当表示更新后的地图，展示出瀑布的路径，其中水流用字符 ~ 表示。

样例

输入样例 1

8 20 3
2 9 15
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOO?OOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOO###OOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOO##O?#O#?O##
OOOOOOOOOOOOOOOOOOOO
####################

输出样例 1

OO~OOOOOO~OOOOO~OOOO
OO~OOOOOO~OOOO?~OOOO
OO~OOOOOO~OO~~~~~OOO
OO~OOOOOO~OO~###~OOO
OO~OOOOO~~~~~~~~~~OO
OO~OOOOO~##~?#~#?~##
~~~~~~~~~~~~~~~~~~~~
####################

输入样例 2

8 20 1
14
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOO?OOOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOO###OOOO
OOOOOOOOOOOOOOOOOOOO
OOOOOOOOO##??#O#?O##
O########OOOOOOOOOOO
#OOOOOOOOOOOOOOOO###

输出样例 2

OOOOOOOOOOOOO~~~OOOO
OOOOOOOOOOOOO~?~OOOO
OOOOOOOOOOOO~~~~~OOO
OOOOOOOOOOOO~###~OOO
OOOOOOOO~~~~~~~~~~OO
~~~~~~~~~##??#~#?~##
~########OOOOO~O~~~~
#OOOOOOOOOOOOO~O~###