1928 - 胆小菇之梦
描述

一个 n \times m 的地图,`I` 表示胆小菇,胆小菇只会向右发射子弹!保证只有一只。

`<`,`>`,`^`,`v` 分别表示射向所指方向的豌豆射手,玉米投手,卷心菜投手,`+` 表示可以同时射向左右两方的裂荚射手,`.` 表示空地。

发射子弹,别的植物当受到子弹攻击时才会发射子弹。

子弹碰到植物就会消失。

你是僵王博士,需要确定哪里没有子弹或植物来投掷小鬼僵尸。


输入

第一行两个正整数 n,m

接下来 n 行,每行一个长度为 m 的字符串,仅包括 `I`,`<`,`>`,`^`,`v`,`+`,`.`。


输出

一个 n \times m 的 01 矩阵,其中 0 表示无子弹或植物,1 表示有子弹或植物。


样例

输入

5 5
.>.+.
.I.^.
.....
.....
....<

输出

0 1 1 1 1
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 <
提示

50%数据,n,m \le 100

100%数据,n,m \le 2000


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 8
通过次数 1