[问题描述]
一次，有2个人准备到一个箭头迷宫里去玩。这个迷宫里有一些箭头（上、下、左、右的箭头分别用n、U、(、)表示）和一些传送门（一对传送门用大小写字母表示）人们在走的时候，会这样走：
（1）如果他前面的一个格子是平地，则他向前走1步。
（2）如果他前面的一个格子是边界或者墙，他就向右转90度，直到前面的格子是平地为止。
（3）如果他前面的一个格子是箭头，则他转向和这个箭头对应的方向。
（4）如果他前面的一个格子是传送门，则他自动进入和它对应的另一个传送门（方向不变）。
（5）如果他前面的一个格子是陷阱（用Q表示，一个迷宫里的陷阱不会超过5个），则他自动退出迷宫。
迷宫有一个入口（用“！”表示）和一个出口（用“#”表示），2个人都从入口进入，从出口退出（第1个人可以从陷阱退出，而第2个人不行）第1个人不会被箭头影响方向，
而第2个人会被箭头影响方向。第1个人退出之后第2个人才可以进入。第1个人可以在任意一个有箭头的地方把箭头右转90度。
时间：任意一个人走1步或者旋转一次箭头都要1秒，进入迷宫或转身不需要额外的时间。

你的任务就是求从第1个人进入到第2个人到达出口一共最短要多长时间（他们不是傻瓜，不会走回头路的）。
[输入]
第一行是2个整数s1、s2（1<=s1<=45，1<=s2<=45），表示迷宫的长和宽。第2行是3个整数t1、t2、t3（0<=t1<=20、0<=t2<=12、0<=t3<=5），分别表示迷宫中箭头的个数，传送门的对数和陷阱的个数。
接下来s1行每行s2个字符，表示迷宫数据。其中：
{*}表示墙壁。
{!}{#}分别表示入口和出口。
{n}{U}{(}{)}表示四个方向的箭头。
{Aa}{Bb}{Cc}…表示一对传送门。
{Q}表示陷阱。
{ }表示平地。
[输出]
一个整数：从第1个人进入到第2个人到达出口最短要耗费的时间（单位：秒）
[样例输入]
8 8
3 2 1
  *  a**
 *  *b #
 *Q n **
  (    B
**     *
**  ** *
  (***A*
!*******
[样例输出]
23