Problem G
Where's My Waterfall?

As a level designer for Super Mawio Bros, you have been creating maps for Mawio to play on, each with some combination of blank spaces, bricks, and item boxes for Mawio to navigate on his way to save Princess Pweach. You want to make some of the maps more interesting, so you decide to add some waterfalls to them. These waterfalls naturally cascade around the bricks and item boxes that you have already placed as they flow down from the top of the screen.

Currently, the map contains nothing but bricks, item boxes, and blank spaces. Waterfalls will be placed at certain column numbers at the top of the screen. Given this information, output an updated map with the waterfalls displayed. Water flows straight down unless it is obstructed by a brick or item box. When water is obstructed by an obstacle, it will flow to both the right and the left of each obstacle, unless those locations are also obstructed. When water flows to the bottom of the map, it stops flowing at the spot it hits the bottom at.

In the current representation of the map, blank spaces are represented by the character ‘O’, bricks by the character ‘#’, and item boxes by the character ‘?’. In the updated representation, water should be represented by the character ‘$\sim$’. There will be no bricks nor item blocks on the top layer of a level.

Input

The first line containing three space separated integers $n$, $m$, and $k$ ($1\le n,m\le 1000$, $1\le k\le m$). $n$ and $m$ represent the number of rows and columns in the map respectively. $k$ represents the number of waterfalls that are to be added.
The second line contains $k$ space-separated integers with each integer representing the column position $p_k$ ($0\le p_k<m$) of a waterfall that needs to be added at the top of the map.
The next $n$ lines each contain $m$ characters. These $n$ lines represent the $n\times m$ map of the level. Blank spaces are represented by the character ‘O’, bricks by the character ‘#’, and item boxes by the character ‘?’.

Output

Output $n$ lines with each line containing $m$ characters. These lines should represent a map that is updated to show the paths of the waterfalls, where water is represented by the character ‘$\sim$’.

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

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

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

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