You are given an R × C grid. Some cells, marked with ‘#’, have a wall. The rest of cells are free, and they are marked with ‘.’. There are two exceptions: one free cell is marked with ‘S’ (it is your starting position), and another free cell is marked with ‘T’ (it has a treasure).

Your goal is to reach the treasure as fast as possible. Every second, you can either move to an adjancent free cell, or hit an adjancent wall with a hammer. You know that every wall vanishes after H hits.

Input

Input consists of several cases,
each with R, C and H,
followed by R lines with C characters each.
Assume that R and C are between 1 and 1000,
and that H is between 1 and 10^{5}.

Output

For every case, print the minimum time to reach the treasure from the starting position.

Public test cases

**Input**

1 2 20 ST 2 3 10 S.. ..T 2 3 10 S## ##T 3 3 10 T.. ##. S.. 3 3 3 T.. ##. S.. 4 6 100000 T##S#. ..###. ...#.. ......

**Output**

1 3 23 6 5 100013

Information

- Author
- Pol Mauri
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Quinzè Concurs de Programació de la UPC - Semifinal
- Date
- 2017-06-29