【POJ Challenge】翻版玛丽

lqp18_31 和 1tthinking 虽然性格完全不同，但都喜欢玩《Super Mario Bros》。一天，他们玩得正高兴时，Mac 突然坏了，于是便向 ftiasch 借电脑。然而，ftiasch 使用的是 Ubuntu，电脑上没有这个游戏，因此她打算为两个可怜的小朋友编写一个 Mario 游戏。可是写到一半，ftiasch 觉得无聊，便跑去找她的姐妹们玩了。请你帮助 ftiasch 完成这个游戏。

游戏地图是一个包含 $R$ 行、 $C$ 列的字符画布，左下角为坐标原点。一个图形的坐标 $(x,y)$ 表示其外接矩形左下角与地图底边相距 $x$ 行、与地图左边界相距 $y$ 列。

图形中的空格表示透明像素，只有非空格字符参与重叠判断、碰撞检测和地图绘制。输入保证所有初始存在的物体都能完整放入地图，任意两个初始物体均不重叠，并且 Mario 初始时脚下一定有砖块。两个物体重叠，是指它们至少有一对非空格像素位于同一位置。

游戏中共有以下几种图形。

Small Mario：

     ********
    ************
    ####....#.
  #..###.....##....
  ###.......######
     ...........
    ##*#######
 ####*******######
...#***.****.*###....
....**********##.....
....****    *****....
  ####        ####
######        ######

Big Mario：

     ********
    **************
    ####....#.
  #..##.....#.....
  #..###.....##....
  ###.......######
     ...........
    ##*######
  ####*#####*#####
######*******#######
...#***.****.*###....
....**********##.....
...**************....
    ****    ****
  ####        ####
######        ######

蘑菇：

   ########
 ##.*****.##
##...****...##
#............#
#..########..#
###..#..#..###
  #..#..#..#
  #........#
   ########

水管：

####################
#------------------#
#------------------#
####################
    #----------#
    #----------#
    #----------#
    #----------#
    ############

金币：

 ###
#...#
#.#.#
#.#.#
#...#
 ###

砖块：

##############
#...#......#.#
##############
#..#....#....#
##############
#.....#......#
##############
#.#..#....#..#
##############

若将 Mario 当前使用的图形整体向下移动一个像素后，它与某个砖块或水管至少有一对非空格像素重叠，则称该砖块或水管位于 Mario 脚下。二者外接矩形的左边界不必相同。

动作序列包含以下指令：

R：若将 Mario 整体向右移动一个像素后，不会与任何砖块或水管的非空格像素重叠，则令其坐标中的 $y$ 增加 $1$ ；
L：若将 Mario 整体向左移动一个像素后，不会与任何砖块或水管的非空格像素重叠，则令其坐标中的 $y$ 减少 $1$ ；
D：找出所有位于 Mario 脚下的水管。若没有满足条件的水管，则状态不变；若只有一根，则将其作为源水管；若两根水管都满足条件，则按照输入顺序选择 tube1 作为源水管。随后，Mario 被传送到另一根水管的正上方。若目标水管的坐标为 $(x_{\mathrm{tube}},y_{\mathrm{tube}})$ ，则 Mario 的新坐标为 $(x_{\mathrm{tube}}+9,y_{\mathrm{tube}})$ 。传送完成后继续进行重力结算，Mario 可能继续下落；
P：不改变游戏状态，仅用于输出当前地图和得分。

当 Mario 与蘑菇的非空格像素发生重叠时，蘑菇立即消失，Mario 切换为 Big Mario 图形，其外接矩形左下角坐标保持不变。切换图形时不进行砖块或水管的碰撞检查，也不会移动 Mario，因此 Big Mario 新增的非空格像素可能与砖块或水管重叠。此后的支撑判断、移动、金币收集和地图绘制均使用 Big Mario 图形。

当 Mario 与金币的非空格像素发生重叠时，该金币立即消失，Mario 获得 $100$ 分。

如果 Mario 脚下没有砖块或水管，它会在重力作用下不断向下掉落。如果 Mario 已经到达地图底部，并且脚下仍然没有砖块或水管，则 Mario 失败。

失败时必须输出以下图案：

....#####.......#........#...#..#####.........###...#.....#..#####.......#####.....
...#...........#.#......##..##..#............#...#..#....#...#..........#.....#...
...#..........#..#.....#.#.#.#..#####........#...#..#...#....#####.....#######...
...#..###... #####....#..##..#..#............#...#..#..#.....#........#..#......
...#....#...#....#...#...#...#..#............#...#..#.#......#.......#....#....
....###.#..#.....#..#........#..#####.........###...##.......#####..#......#..

绘制当前地图时，依次绘制砖块和水管、仍然存在的金币和蘑菇，最后绘制 Mario。后绘制图形的非空格字符会覆盖同一位置中先绘制的字符。

输入格式

第一行输入两个整数 $R$ 和 $C$ ，表示游戏地图的大小。

第二行输入两个整数 $x_{\mathrm{mario}}$ 和 $y_{\mathrm{mario}}$ ，表示 Small Mario 的初始坐标。

第三行输入两个整数 $x_{\mathrm{mush}}$ 和 $y_{\mathrm{mush}}$ ，表示唯一一个蘑菇的坐标。若 $x_{\mathrm{mush}}$ 或 $y_{\mathrm{mush}}$ 等于 $-1$ ，则蘑菇不存在。

第四行输入四个整数 $x_{\mathrm{tube1}}$ 、 $y_{\mathrm{tube1}}$ 、 $x_{\mathrm{tube2}}$ 和 $y_{\mathrm{tube2}}$ ，表示两根水管的坐标。若相应坐标等于 $-1$ ，则对应的水管不存在。

第五行首先输入一个整数 $n$ ，表示砖块数量，随后输入 $n$ 对整数，第 $i$ 对表示第 $i$ 个砖块的坐标。

第六行首先输入一个整数 $m$ ，表示金币数量，随后输入 $m$ 对整数，第 $i$ 对表示第 $i$ 枚金币的坐标。

第七行输入一个字符串，表示动作序列。该字符串仅包含字符 D、L、R 和 P。

输出格式

按照顺序处理动作序列。处理第 $i$ 个字符前，其中下标从 $i=0$ 开始，若 $i=0$ 或该字符为 P，则输出一次当前地图和得分。即使第一个字符就是 P，也只输出一次。指令 P 本身不改变游戏状态。

每次输出地图时，从上到下输出恰好 $R$ 行。保留每行的前导空格以及非空字符之间的空格，删除该行最右侧非空字符之后的所有空格。若一行全为空格，则输出一个空行。

输出地图后，再输出一行：

Mario : ? points

其中 ? 表示 Mario 当前的得分。

如果处理 L、R 或 D 后 Mario 失败，则输出题目描述中给出的六行失败图案，并立即停止，不再处理后续字符。

任意相邻的两个输出块之间恰好包含一个空行。地图及其后的得分共同构成一个输出块，失败图案构成一个输出块。

样例输入

100 150
9 0
-1 -1
0 42 0 90
4 0 0 0 14 0 28 0 76
5 12 28 12 62 12 76 12 90 12 42
RRRRRRRRRRRP

样例输出















































































     ********
    ************
    ####....#.
  #..###.....##....
  ###.......######           ###           ###                 ###           ###           ###
     ...........            #...#         #...#               #...#         #...#         #...#
    ##*#######              #.#.#         #.#.#               #.#.#         #.#.#         #.#.#
 ####*******######          #.#.#         #.#.#               #.#.#         #.#.#         #.#.#
...#***.****.*###....       #...#         #...#               #...#         #...#         #...#
....**********##.....        ###           ###                 ###           ###           ###
....****    *****....
  ####        ####
######        ######
##############################################################              ##################################
#...#......#.##...#......#.##...#......#.##------------------#              #...#......#.##------------------#
###########################################------------------#              ###############------------------#
#..#....#....##..#....#....##..#....#....#####################              #..#....#....#####################
##########################################    #----------#                  ##############    #----------#
#.....#......##.....#......##.....#......#    #----------#                  #.....#......#    #----------#
##########################################    #----------#                  ##############    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#                  #.#..#....#..#    #----------#
##########################################    ############                  ##############    ############
Mario : 0 points















































































                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###                 ###           ###           ###
                ...........               #...#               #...#         #...#         #...#
               ##*#######                 #.#.#               #.#.#         #.#.#         #.#.#
            ####*******######             #.#.#               #.#.#         #.#.#         #.#.#
           ...#***.****.*###....          #...#               #...#         #...#         #...#
           ....**********##.....           ###                 ###           ###           ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################              ##################################
#...#......#.##...#......#.##...#......#.##------------------#              #...#......#.##------------------#
###########################################------------------#              ###############------------------#
#..#....#....##..#....#....##..#....#....#####################              #..#....#....#####################
##########################################    #----------#                  ##############    #----------#
#.....#......##.....#......##.....#......#    #----------#                  #.....#......#    #----------#
##########################################    #----------#                  ##############    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#                  #.#..#....#..#    #----------#
##########################################    ############                  ##############    ############
Mario : 100 points

数据范围

$1\le R,C\le 300$ ；
$0\le x_{\mathrm{mario}}<R$ ， $0\le y_{\mathrm{mario}}<C$ ；
输入保证所有初始存在的物体均能完整放入地图；
输入保证任意两个初始物体均不重叠；
输入保证 Mario 初始时脚下一定有砖块。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

100 150
9 0
-1 -1
0 42 0 90
4 0 0 0 14 0 28 0 76
5 12 28 12 62 12 76 12 90 12 42
RRRRRRRRRRRP

输出















































































     ********
    ************
    ####....#.
  #..###.....##....
  ###.......######           ###           ###                 ###           ###           ###
     ...........            #...#         #...#               #...#         #...#         #...#
    ##*#######              #.#.#         #.#.#               #.#.#         #.#.#         #.#.#
 ####*******######          #.#.#         #.#.#               #.#.#         #.#.#         #.#.#
...#***.****.*###....       #...#         #...#               #...#         #...#         #...#
....**********##.....        ###           ###                 ###           ###           ###
....****    *****....
  ####        ####
######        ######
##############################################################              ##################################
#...#......#.##...#......#.##...#......#.##------------------#              #...#......#.##------------------#
###########################################------------------#              ###############------------------#
#..#....#....##..#....#....##..#....#....#####################              #..#....#....#####################
##########################################    #----------#                  ##############    #----------#
#.....#......##.....#......##.....#......#    #----------#                  #.....#......#    #----------#
##########################################    #----------#                  ##############    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#                  #.#..#....#..#    #----------#
##########################################    ############                  ##############    ############
Mario : 0 points















































































                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###                 ###           ###           ###
                ...........               #...#               #...#         #...#         #...#
               ##*#######                 #.#.#               #.#.#         #.#.#         #.#.#
            ####*******######             #.#.#               #.#.#         #.#.#         #.#.#
           ...#***.****.*###....          #...#               #...#         #...#         #...#
           ....**********##.....           ###                 ###           ###           ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################              ##################################
#...#......#.##...#......#.##...#......#.##------------------#              #...#......#.##------------------#
###########################################------------------#              ###############------------------#
#..#....#....##..#....#....##..#....#....#####################              #..#....#....#####################
##########################################    #----------#                  ##############    #----------#
#.....#......##.....#......##.....#......#    #----------#                  #.....#......#    #----------#
##########################################    #----------#                  ##############    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#                  #.#..#....#..#    #----------#
##########################################    ############                  ##############    ############
Mario : 100 points