Description

一个n*m的矩阵中，有许多的建筑，其中也包含了停车场，继上次龙卷风事故后，政府决定加固一些停车场，加固后的停车场需要破坏两次才能算真真的破坏。谁也没想到这个矩阵中出现了比上次还强的龙卷风，它能影响周围一圈的位置，它能将普通的停车场直接吹飞，但是加固后的得被两个及以上的龙卷风影响才能被吹飞，龙卷风随机出现在矩阵中。

Format

Input

第 1 行输入两个数字，n和m，代表矩阵的大小（1 <= n，m <= 200）

第 2 行到第 n + 1 行，每行 m 个字符，不同字符携带了不同的信息，代表矩阵里的内容。

“ # ”代表停车场，“ ? ”代表龙卷风，“%”代表加固后的停车场，其余字符代表城市的其他建筑物

注意：龙卷风的影响范围为龙卷风周围的一圈而不是十字。

Output

首先从第一行开始从左到右，如果有安全的停车场（加固的停车场只被破坏了一次也算安全），输出他的二维下表（下标从1开始），直到第n行。每行占一行。

接下来输出龙卷风来之后的新矩阵。

新矩阵，即：在原矩阵中，如果有停车场处于龙卷风的作用范围内，“ # ”和破坏了两次的“%” 应被更改成 “ * ” ，只被破坏了一次的停车场“%”变为“#”（因为飞上天了所以看不见了）；同时对于每一个龙卷风 “ ? ” 更改成能摧毁的停车场的数量（只被破坏了一次的停车场不算被摧毁）

注意：两个龙卷风影响一个加固停车场第二个影响的龙卷风破坏的数量会加1而第一个龙卷风则不会加一。如样例2中a[1][3]的龙卷风“?“能破坏的停车场的数量为1而不是3，但是a[1][4]的龙卷风能破坏3个因为a[2][3],a[2][4]的“%”被a[1][3]破坏变为了”#“再被”?”摧毁原本a[1][5]又有个“#”。

Samples

3 3
#%#
#?#
#%#

1 2
3 2
*#*
*6*
*#*

4 5
##??#
%k%%%
%##?#
?%d%s

1 1
2 1
3 1
4 2
4 4
#*13*
%k***
#**3*
1#d#s

Hint