Art Installation

You are given a park represented as a grid with R rows and C columns. Each cell of the grid is either a tree (denoted by 'T') or an empty space (denoted by '.'). Your task is to determine whether it is possible to install K art pieces on different trees such that the Euclidean distance between any two art pieces is at least \(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \ge D\).

The problem requires you to select K trees from the grid, and for every pair of selected trees, the Euclidean distance (i.e. \(\sqrt{(\Delta r)^2 + (\Delta c)^2}\)) must be no less than D, where \(D\) is provided as input.

If such a placement exists, output YES; otherwise, output NO.

inputFormat

The input is given via standard input (stdin) in the following format:

R C K
row_1
row_2
... 
row_R
D

where:

• R, C, and K are integers representing the number of rows, columns and the number of art pieces to place, respectively.
• Each of the next R lines is a string of length C that represents a row of the park grid, where 'T' indicates a tree and '.' indicates an empty cell.
• D is a number (which may be a floating point value) representing the minimum required Euclidean distance between any two art pieces.

outputFormat

Output a single line to standard output (stdout):

YES

if it is possible to place the art pieces meeting the distance constraint, otherwise output:

NO

## sample

5 5 3
T.T..
.TT.T
.....
.T.T.
TTTTT
2

YES

</p>