Reach the Target with Limited Wall Destruction

You are given a grid representing a battlefield with n rows and m columns. Each cell in the grid is one of the following characters:

• S: the starting position.
• T: the target position.
• .: an empty cell.
• #: a wall that can be destroyed.
• E: an enemy cell which blocks the destruction ability.

You can move up, down, left, or right, but you may only step into an empty cell (or directly into the target cell). If an adjacent cell is a wall, you can use a special ability to destroy a contiguous sequence of wall cells in that direction. This ability works as follows: when you are adjacent to a wall and you have remaining uses (at most k times in total), your attack will clear a sequence of wall cells in that direction until you encounter an empty cell or the target cell. However, if an enemy cell (E) is encountered during the destruction, your attack stops immediately and you cannot proceed in that direction.

Your task is to determine whether it is possible to reach the target cell T from the starting cell S by moving through empty cells and using the destruct ability at most k times.

inputFormat

The first line contains three integers n, m, and k indicating the number of rows, the number of columns, and the maximum number of times you can use your ability.

Then follow n lines, each containing a string of length m that represents a row of the grid.

outputFormat

Output a single line containing YES if it is possible to reach the target cell, otherwise output NO.

5 5 2
S....
#####
##..#
....#
..T##

YES