Problem I
Mild Injury Star

Small maze by Brent Yorgey, CC-BY 4.0

Ivan is speedrunning his favorite video game, Stellar Skirmishes: The Game. The slightly annoying villain, Garth Wader, plans to use his giant moon-sized space station to block out all sunlight in a specific spot on the peaceful planet of Algernon! In order to prevent this irritating plan, Ivan’s character has infiltrated the space station and inserted a computer virus which will cause the station’s thrusters to fire slightly, changing its trajectory enough to move its shadow to a different spot.

Now he just needs to escape! The rooms on Ivan’s current floor are arranged in a square grid. Ivan is currently at the room in the top left corner of the map and needs to reach the bottom right corner of the map. Between each pair of horizontally or vertically adjacent rooms there is a blast door which can close, blocking Ivan’s passage between those rooms. All the blast doors are currently open, but the alarm has just gone off, and Ivan knows (from playing this game many, many times) the exact time at which various blast doors will close after the alarm is triggered. It takes Ivan one second to move from one room to a vertically or horizontally adjacent room if the blast door is open; if he arrives in a room at time $t$, he can move to an adjacent room only through passages whose blast door closes at time $t+1$ or later (or passages with no blast door), arriving in the adjacent room at time $t+1$.

Help him figure out the best time he can achieve!

Input

The first line of input contains three integers $r$, $c$, and $n$ ($1 \leq r, c \leq 500$; $0 \leq n \leq 10^5$), where $r$ and $c$ are the number of rows and columns in the grid, respectively, and $n$ is the number of blast doors.

Each of the next $n$ lines describes one blast door. A blast door will be described by two integers $i$ and $j$ ($0 \leq i < r$, $0 \leq j < c$) giving the row and column of a room, followed by a single character which is either ‘S’ or ‘E’, and finally an integer $t$ ($0 \leq t \leq 10^6$), the time at which the blast door closes.

• ‘S’ indicates that the blast door is on the south side of the room at coordinates $(i,j)$, between it and the room at $(i+1,j)$. In this case it is guaranteed that $i+1 < r$.

• ‘E’ indicates that the blast door is on the east side of the room at coordinates $(i,j)$, between it and the room at $(i,j+1)$. In this case it is guaranteed that $j+1 < c$.

There will be at most one blast door in any given location. Ivan starts in room $(0,0)$ at time $0$, and the exit is in room $(r-1, c-1)$.

Output

Output the earliest time at which Ivan can reach the exit room. If it is not possible for Ivan to reach the exit room, print “March the 30th be with you!”

2 2 0

2

2 2 1
0 0 S 0

2

2 2 3
0 0 S 0
0 0 E 1
0 1 S 1

March the 30th be with you!