Hide

Problem D
Ads

Web pages are littered with ads (advertisements) these days. You wrote a simple program to detect images which are ads and remove them.

Characters that are any of the following are allowed in images:

  • alphanumeric characters

  • question mark ‘?’

  • exclamation mark ‘!’

  • comma ‘,’

  • full stop ‘.’

  • whitespace ‘ ’

Any images contained characters that are not allowed are considered ads, and will be removed by your program. The ‘$+$’ character will be used only as the border of an image.

All images will follow these rules:

  • They are all axis-aligned rectangles with ‘$+$’ as its border and is at least $3 x 3$ big (including the borders).

  • All ‘$+$’ characters belong to the border of exactly 1 image.

  • Borders of different images will not be adjacent to each other (contact at their corners is also not allowed).

  • They can contain other images while adhering to the rules above.

  • For every banned character that is found inside at least one image, in order not to remove too many unnecessary parts of the images on the web page, you decide that the smallest image (in terms of pixel count) that contains that character will be flagged as an ad and removed.

  • When an ad is removed, every character inside the ad and the border is replaced with a whitespace.

Note that the web page is not considered an image. Characters found on the web page that is not in any image should not be removed.

Input

The first line of the input contains $1 \leq H \leq 200$ and $1 \leq W \leq 200$, the height and width of the web page to be processed respectively. $H$ lines follow, each line contain exactly $W$ ASCII characters whose ASCII decimal value fall in the range $[32, 126]$.

Output

Output the web page with all the ads removed. Do not print extra spaces or new lines.

Subtasks

  1. (21 Points): There is no ads in the web page at all.

  2. (21 Points): There is either one image or no image in the web page.

  3. (28 Points): No images will be found inside other images.

  4. (30 Points): No additional constraint.

Sample Input 1 Sample Output 1
8 20
 apples are great!  
++++++++++++++++++++
+ oranges are      +
+ way better!      +
+ #oranges>apples  +
++++++++++++++++++++
 check out our      
 fresh apples!      
 apples are great!  
                    
                    
                    
                    
                    
 check out our      
 fresh apples!      
Sample Input 2 Sample Output 2
7 7
+++++++
+  =  +
+ +++ +
+ + + +
+ +++ +
+     +
+++++++
       
       
       
       
       
       
       
Sample Input 3 Sample Output 3
7 7
+++++++
+     +
+ +++ +
+ +=+ +
+ +++ +
+     +
+++++++
+++++++
+     +
+     +
+     +
+     +
+     +
+++++++

Please log in to submit a solution to this problem

Log in