A4967 | 午枫爱迷宫

小午和小枫掉入了一个大小为 $n\times m$ 的充满陷阱的迷宫，小枫不幸被机关锁住了，迷宫中有一把可以打开锁住小枫机关的钥匙、一些墙壁、一些安全的道路、一些较高的障碍物和一个出口。

小午现在知道了整个迷宫样貌，他用不同的符号把整个迷宫画了下来，其中各个符号所代表的意义如下：

. ：表示安全的道路。

# ：表示墙壁。

N ：表示小午所在位置。

M ：表示小枫所在位置。

! ：表示钥匙。

$ ：表示较高的障碍物。

@ ：表示出口。

小午和被解救的小枫每次可以走到其相邻的道路，比如，若当前位置为 $(x,y)$ ，则其在不受阻的前提下可以移动到 $(x+1,y)$，$(x-1,y)$，$(x,y+1)$，$(x,y-1)$ 这四个位置的其中一个。

由于他身材矮小，无法通过那些较高的障碍物，但是小枫可以带他一起翻越那些障碍物，所以如果小午想通过那些障碍物的话必须先解救小枫。其中 N 、M 、! 、@ 所在位置也是一个安全的道路，所以当小午或小枫走到这些位置时并不会受到任何额外的限制。小午想知道他能否解救小枫并和他一起逃出这个迷宫，当然，如果小午想尽一切方法也无法解救小枫但自己可以逃出迷宫的话，他会选择抛弃小枫独自逃出迷宫。

第一行输入两个正整数 $n,m$ 表示迷宫的行数和列数 $(1\leq n, m \leq 10^3)$ 。

接下来 $n$ 行，每行 $m$ 个字符 $s_{i,j}$ ，保证 $s_{i,j} \in \{'.','\#','N','M','!','\$ ','@'\}$，其中 'N'，'M'，'!'，'@' 保证有且仅有一个。

输出一行字符串，如果小午可以解救小枫并一起跳出迷宫，输出 " we were here together" ；如果小午无法解救小枫，但可以自己独自逃出迷宫的，输出 "sorry" ；如果两人都无法逃出迷宫，输出 "NO" 。