1928 - 胆小菇之梦
Description

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

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

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

子弹碰到植物就会消失。

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


Input

第一行两个正整数 n,m

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


Output

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


Examples

Input

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

Output

0 1 1 1 1
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 <
Hint

50%数据,n,m \le 100

100%数据,n,m \le 2000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 8
通过次数 1