Assassin’s Quest in the Forbidden Palace

After several years, the assassin Jing Ke returns to the Xianyang Palace to attempt an assassination of Qin Shi Huang. The palace can be modeled as a rectangle with n rows and m columns. We set up a coordinate system such that in each row the x‐axis increases from left to right and in each column the y‐axis increases from bottom to top, with the bottom‐left cell having coordinate \((1,1)\).

Each cell in the grid can be one of the following four types:

1. Start: Jing Ke’s initial position, indicated by character S.
2. Target: The location of Qin Shi Huang, indicated by character T.
3. Guard: A guard is denoted by a positive integer \(a_{i,j}\). A guard located at \((i,j)\) can observe any cell \((x,y)\) satisfying \[ |x-i|+|y-j| < a_{i,j}. \] In other words, the guard observes all cells within a Manhattan distance strictly less than \(a_{i,j}\) from his position. Note that a cell containing a guard is always impassable.
4. Empty cell: Represented by .

Normally, every second Jing Ke can move to any one of the eight adjacent cells (i.e. a king’s move in chess). However, when moving normally, he cannot step into any cell which either contains a guard or lies in the observation range of any guard, and he must always remain within the grid boundaries \(1\le x\le m\) and \(1\le y\le n\).

Jing Ke also has two skills which he may use at the time of movement:

1. Stealth: When activated, the next second Jing Ke becomes invisible so that guards will not observe him. This allows him to enter cells that would otherwise be under observation (though he still cannot enter a cell with a guard). This state lasts for only one second.
2. Teleport: When activated, in the next second his movement is modified to a jump of exactly distance \(d\) in one of the four cardinal directions (up, down, left, or right), i.e. to one of \[ (x+d,y),\quad (x-d,y),\quad (x,y+d),\quad (x,y-d). \]

Both skills can be used simultaneously and there is no cooldown between uses. However, each skill has a usage limit. It is not necessary to use all allotted uses.

In summary, a move takes one second. There are four kinds of moves:

• Normal move without any skill: Move one step in any of the eight directions. The destination cell must be within the grid, must not contain a guard, and must not be observed by any guard.
• Normal move with stealth: Same as a normal move but by spending one stealth usage the observation restrictions are ignored (the destination cell still must not contain a guard).
• Teleport move without stealth: Jump exactly \(d\) cells in one of the four cardinal directions. In this case the destination cell (which must be within the grid and must not contain a guard) is subject to guard observation.
• Teleport move with stealth: As above, but by spending one stealth usage the observation check is ignored.

Given the map of Xianyang Palace and the parameters below, compute the optimal way for Jing Ke to reach Qin Shi Huang’s position. The primary objective is to minimize the total time (in seconds). If there are several ways which take the same time, he wants the one that minimizes the total number of skills (stealth + teleport) used. In case there is still a tie, he wants to minimize the number of stealth uses.

If it is impossible for Jing Ke to reach his target, output -1.

inputFormat

The first line contains five integers: n m d p q where:

• n is the number of rows and m is the number of columns of the grid.
• d is the teleport distance.
• p is the maximum number of times the stealth skill can be used.
• q is the maximum number of times the teleport skill can be used.

Then follow n lines, each containing m tokens separated by spaces. Each token is either S (start), T (target), . (empty cell) or a positive integer representing a guard (with its watch radius a_i,j). The first of these n lines corresponds to the top row (i.e. y=n) and the last corresponds to the bottom row (i.e. y=1). Note that the grid’s coordinates follow the convention with \((1,1)\) at the bottom‐left corner.

outputFormat

If Jing Ke can reach the target, output three space-separated integers:

• The minimum time (in seconds).
• The total number of skills used (stealth + teleport).
• The number of times the stealth skill was used.

If it is impossible, output -1.

sample

3 3 2 1 1
. 1 .
. . .
S . T

2 1 0