CF1423D.Does anyone else hate the wind?

Mark and his crew are sailing across the sea of Aeolus (in Greek mythology Aeolus was the keeper of the winds). They have the map which represents the $N$x$M$ matrix with land and sea fields and they want to get to the port (the port is considered as sea field). They are in a hurry because the wind there is very strong and changeable and they have the food for only $K$ days on the sea (that is the maximum that they can carry on the ship). John, the guy from Mark's crew, knows how to predict the direction of the wind on daily basis for $W$ days which is enough time for them to reach the port or to run out of the food. Mark can move the ship in four directions (north, east, south, west) by one field for one day, but he can also stay in the same place. Wind can blow in four directions (north, east, south, west) or just not blow that day. The wind is so strong at the sea of Aeolus that it moves the ship for one whole field in the direction which it blows at. The ship's resulting movement is the sum of the ship's action and wind from that day. Mark must be careful in order to keep the ship on the sea, the resulting movement must end on the sea field and there must be a 4-connected path through the sea from the starting field. A 4-connected path is a path where you can go from one cell to another only if they share a side.

For example in the following image, the ship can't move to the port as there is no 4-connected path through the sea.

In the next image, the ship can move to the port as there is a 4-connected path through the sea as shown with the red arrow. Furthermore, the ship can move to the port in one move if one of the following happens. Wind is blowing east and Mark moves the ship north, or wind is blowing north and Mark moves the ship east. In either of these scenarios the ship will end up in the port in one move.

Mark must also keep the ship on the map because he doesn't know what is outside. Lucky for Mark and his crew, there are $T$ fish shops at the sea where they can replenish their food supplies to the maximum, but each shop is working on only one day. That means that Mark and his crew must be at the shop's position on the exact working day in order to replenish their food supplies. Help Mark to find the minimum of days that he and his crew need to reach the port or print $-1$ if that is impossible with the food supplies that they have.

马克和他的船员正在爱琴海上航行（在希腊神话中，埃俄罗斯是风的守护者）。他们拥有一张地图，该地图是一个 $N \times M$ 的矩阵，其中包含陆地和海洋格子，而他们的目标是抵达港口（港口被视为一个海洋格子）。由于当地风力强劲且多变，他们必须尽快抵达，船上仅储备了 $K$ 天的食物（即船上最多可携带 $K$ 天的食物量）。马克船员中的约翰能够预测未来 $W$ 天内每日的风向，这一预测时间足够他们抵达港口或耗尽食物。

马克每天可以操控船只向四个方向之一（北、东、南、西）移动一格，也可以选择原地不动。风同样可能从四个方向之一（北、东、南、西）吹来，或者当天无风。由于埃俄罗斯海域风力极强，若当日有风，则船只将被风推动整整一格，方向与风向一致。船只的最终位移等于马克的操控位移与当日风力位移的矢量和。

马克必须谨慎操作，确保船只始终停留在海洋格子上：每次移动后的最终位置必须落在海洋格子内，且起点与终点之间必须存在一条由海洋格子构成的 4-连通路径。所谓 4-连通路径，是指路径中相邻格子必须共享一条边（即上下左右相邻）。

例如，在下图中，船只无法抵达港口，因为起点与港口之间不存在一条完全由海洋格子组成的 4-连通路径。

而在下图中，起点与港口之间存在一条由海洋格子构成的 4-连通路径（如红色箭头所示），因此船只可以抵达港口。此外，若满足以下任一条件，船只可在一天内直接抵达港口：风向东吹且马克操控船只向北移动；或风向北吹且马克操控船只向东移动。在这两种情形下，船只的合成位移均将使其恰好停靠在港口格子上。

马克还必须确保船只始终位于地图范围内，因为他不知道地图之外的情况。幸运的是，海面上共有 $T$ 家渔店，可在船只经过时为其补满食物至最大容量，但每家渔店仅在指定的一天营业。这意味着，马克及其船员必须在渔店营业的当天恰好位于该渔店所在格子，才能完成补给。

请帮助马克计算其船队抵达港口所需的最少天数；若在现有食物限制下无法抵达，则输出 $-1$。

First line contains two integer numbers $N$ and $M$ ($1 \leq N, M \leq 200$) - representing the number of rows and number of columns of the map.

Second line contains three integers, $K$ ($0 \leq K \leq 200$) which is the number of days with the available food supplies, $T$ ($0 \leq T \leq 20$) which is the number of fields with additional food supplies and $W$ ($0 \leq W \leq 10^6$) which is the number of days with wind information.

Next is the $N$x$M$ char matrix filled with the values of 'L', 'S', 'P' or 'M'. 'L' is for the land and 'S' is for the sea parts. 'P' is for the port field and 'M' is the starting field for the ship.

Next line contains $W$ chars with the wind direction information for every day. The possible inputs are 'N' - north, 'S' - south, 'E' - east, 'W' - west and 'C' - no wind. If Mark's crew can reach the port, it is guaranteed that they will not need more than $W$ days to reach it.

In the end there are $T$ lines with the food supplies positions. Each line contains three integers, $Y_i$ and $X_i$ ($0 \leq Y_i \lt N, 0 \leq X_i \lt M$) representing the coordinates (Y is row number and X is column number) of the food supply and $F_i$ ($0 \leq F_i \leq 10^6$) representing the number of days from the starting day on which the food supply is available.

第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq 200$），分别表示地图的行数和列数。

第二行包含三个整数：$K$（$0 \leq K \leq 200$）表示有食物补给的天数，$T$（$0 \leq T \leq 20$）表示拥有额外食物补给的格子数量，$W$（$0 \leq W \leq 10^6$）表示提供风向信息的天数。

接下来是一个 $N \times M$ 的字符矩阵，其中每个元素为 'L'、'S'、'P' 或 'M'。'L' 表示陆地，'S' 表示海洋，'P' 表示港口格子，'M' 表示船只的起始位置。

下一行包含 $W$ 个字符，表示每一天的风向信息。可能的输入为：'N'（北）、'S'（南）、'E'（东）、'W'（西）和 'C'（无风）。若 Mark 的船员能够抵达港口，则保证其所需天数不超过 $W$ 天。

最后是 $T$ 行，每行描述一处食物补给的位置。每行包含三个整数：$Y_i$ 和 $X_i$（$0 \leq Y_i < N,\ 0 \leq X_i < M$），表示该食物补给的坐标（$Y$ 为行号，$X$ 为列号）；以及 $F_i$（$0 \leq F_i \leq 10^6$），表示该食物补给自起始日起第 $F_i$ 天开始可用。

One integer number representing the minimal days to reach the port or $-1$ if that is impossible.

一个整数，表示到达港口所需的最少天数；如果无法到达，则为 $-1$。