Problem Description

Years later, the assassin Jing Ke returns to the Xianyang Palace, attempting to assassinate Ying Zheng.

The map of Xianyang Palace can be described as a rectangle with \( n \) rows and \( m \) columns. Here, we define the positive direction of the \( x \)-axis from left to right in each row, and the positive direction of the \( y \)-axis from bottom to top in each column, with the bottom-left corner point having coordinates \( (1,1) \). Points in the rectangle can be classified into 4 types:

1. Starting point, which is where Jing Ke is located, represented by the character S on the map.
2. Ending point, which is where Ying Zheng is located, represented by the character T on the map.
3. Guards, represented by a positive integer \( a_{i,j} \) on the map. A guard \( (i,j) \) can observe points within a Manhattan distance less than \( a_{i,j} \). That is, guard \( (i,j) \) can observe all points \( (x,y) \) satisfying \( |x-i| + |y-j| < a_{i,j} \).
4. Empty spaces, represented by the character . on the map.

Jing Ke's normal movement is to move one cell in any of the eight connected directions per second. As shown in the figure below, the center point is where Jing Ke is currently located, and each second, he can move to any of the other eight points.

It should be noted that during normal movement, Jing Ke cannot step into any cell that is either occupied by a guard or within a guard's observation. Of course, he cannot leave the Xianyang Palace, meaning that at any time, Jing Ke's coordinates \( (x,y) \) must satisfy \( 1 \le x \le m \) and \( 1 \le y \le n \).

Jing Ke has two skills: invisibility and teleportation.

1. Invisibility: Jing Ke enters an invisible state the next second, where guards cannot observe him. He can enter the observation range of guards but still cannot enter the cell occupied by a guard. This state lasts only one second.
2. Teleportation: Jing Ke's movement distance changes to \( d \) the next second, but he can only move in the four cardinal directions: \( (x+d,y) \), \( (x-d,y) \), \( (x,y+d) \), \( (x,y-d) \).

In this problem, both skills can be used simultaneously without considering cooldown times, meaning they can be used immediately after the previous use, and there are limits to the number of times each skill can be used. You do not have to use all the available times.

Given the map of Xianyang City, calculate the shortest time for Jing Ke to reach the point where the King of Qin is located. Additionally, if there are multiple solutions with the same time, Jing Ke prefers to use the least total number of both skills; if there are still multiple solutions, he prefers to use the least number of invisibility skills.

Input Format

The first line contains five integers \( n \), \( m \), \( c_1 \), \( c_2 \), \( d \), representing the size of the map \( n \times m \), the limit on the number of times invisibility can be used \( c_1 \), the limit on the number of times teleportation can be used \( c_2 \), and the distance of one teleportation \( d \).

The next \( n \) lines, each containing \( m \) elements. Each element is either a character S, T, . or a positive integer \( a_{i,j} \), representing a grid point, with specific meanings detailed in the problem description.

Output Format

If Jing Ke cannot reach the point where the King of Qin is located, output a single line containing \(-1\).

Otherwise, output a single line containing three integers \( t \), \( u_1 \), \( u_2 \), representing the shortest time required, the number of times invisibility is used, and the number of times teleportation is used, respectively.

Sample Input and Output

Sample Input #1

5 4 0 0 5
. 1 T 1
. . . 2
. 1 . .
S . . .
1 . . .

Sample Output #1

3 0 0

Sample Input #2

8 6 2 3 3
. S . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
2 . 2 . 2 .
. . 1 . T .
3 . 1 . . 3

Sample Output #2

3 1 3

Sample Input #3

8 6 5 5 2
. S . . . .
. . . . . .
. . . . . .
1 1 3 2 . 1
2 3 2 2 1 3 
3 2 4 1 4 3 
2 6 1 5 T 2 
8 1 6 3 2 10

Sample Output #3

-1

Notes/Hints

Sample 1 Explanation

The starting point is \( (1,2) \). Jing Ke can reach the ending point by moving sequentially to \( (1,3) \), \( (2,4) \), \( (3,5) \).

Sample 2 Explanation

The starting point is \( (2,8) \). Jing Ke can reach the ending point by moving sequentially to \( (2,5) \), \( (2,2) \), \( (5,2) \). Note that even though the last step reaches the ending point, since it is within the guard's observation range, invisibility is still required to enter.

Data Range and Hints

For test points \( 1 \sim 6 \): \( n \), \( m \le 10 \), \( c_1 = c_2 = 0 \), the shortest time required is guaranteed to be no more than 5 or there is no solution.

For test points \( 7 \sim 10 \): \( n \), \( m \le 20 \), \( c_1 = c_2 = 0 \), the position of T is guaranteed to be outside the observation range of any guard.

For test points \( 11 \sim 12 \): \( n \), \( m \le 20 \), \( c_1 = 0 \).

For test points \( 13 \sim 14 \): \( n \), \( m \le 20 \), \( c_1 \), \( c_2 \le 5 \).

For test points \( 15 \sim 16 \): The number of guards does not exceed 350.

For all test points: \( 2 \le n \), \( m \le 350 \), \( 1 \le a_{i,j} \le 350 \), \( 0 \le c_1 \), \( c_2 \le 15 \), \( 1 \le d \le 350 \).

The position of S is guaranteed to be outside the observation range of any guard.

见题面 Input 部分

见题面 Output 部分