This page is still under construction.

Parts of this page are still being built. What you see may change.

Deceptive Directions

Time limit2sMemory limit1024 MB

Summary
Given a grid and a sabotaged instruction string where each step was replaced by a different direction, mark every cell that could be the treasure.
Level

Hard8 of 10

Topics
BFS, Graph, Implementation, Matrix
Solved
No attempts yet

Problem

You are stranded on a remote island, searching for a legendary lost treasure. You have gotten your hands on directions that lead straight to the treasure, but there is a problem. A saboteur in your expedition edited the precious directions at some point, so they may no longer lead to the treasure.

The island can be viewed as a rectangular grid, and the directions are a sequence of east, west, north, and south steps to take in this grid from a given starting position. These directions lead straight to the treasure (though they may involve walking around obstacles) in the sense that there is no shorter way of reaching the treasure. However, the saboteur has arbitrarily replaced each step of the directions with a step in one of the other three directions. In other words, every "west" step has been replaced by "east", "north", or "south". This replacement was done independently for each step, so one "west" may have been replaced by "north" and another by "south", and so on.

Because of this sabotage, the directions seem useless. Maybe they can still be used to narrow down the search. Write a program to find all possible locations of the treasure.

Input

The first line of input consists of two integers ww and hh (3≤w,h≤10003 \le w, h \le 1000), the width and height of the map. Then follow hh lines, each containing ww characters, describing the map. Each such character is either a '.' symbolizing a walkable space, '#' symbolizing an obstacle such as a body of water, dense forest, or a mountain, or 'S' symbolizing the starting point of the directions.

Finally, there is a line containing a string II (1≤∣I∣≤1051 \le |I| \le 10^5) consisting only of the characters 'NWSE', giving the faulty instruction sequence.

The map has exactly one 'S' and its boundary consists only of obstacle cells. The faulty instruction sequence is such that there is at least one possible location of the treasure.

Output

Output the map in the same format as the input (without the first line specifying the dimensions), with all possible locations of the treasure indicated by exclamation marks ('!').

Examples2

  1. Example 1

    Input
    5 5
#####
#...#
#.S.#
#...#
#####
N
    Expected output
    #####
#...#
#!S!#
#.!.#
#####

  2. Example 2

    Input
    7 5
#######
#..#..#
#..S..#
#..#..#
#######
ESS
    Expected output
    #######
#!.#..#
#..S..#
#..#..#
#######