Codah ClubGyakorolj. Küldd be. Fejlődj.
Bejelentkezés
Magyar
#000078

kredit

Professor Djuric: Hellooooo!
Dragance: Good afternoon Professor, It's Dragance.
Professor Djuric: What are you doing, boy?
Dragance: I was just walking in the park and when I arrived at the fountain, I got an idea
about the problem we were talking about...
Professor Djuric: Did you?


That is how the phone conversation continued, which lasted for K minutes, and who knows how much longer it would have lasted if Dragance did not run out of battery. Dragance immediately went to charge his phone, and he went to the nearest electrical outlet in the park to plug in his charger. As soon as he arrives and plugs in his phone he will call the professor again. Professor Djuric wants to organize his time well and he needs a good estimation for how much time Dragance will need before he can call him again.


InputProfessor Djuric and Dragance both know the layout of the park, which is given in the shape of a rectangular matrix with dimensions N x M . The first line of the standard input contains the numbers N and M . In the second line of the standard input is the number K . In the next N lines there are M characters, which mark spots on the map. Allowed characters are 'F', 'x', '.' and 'T'. The character 'F' marks the fountain. All objects that act as a blockade (lake, stadium, flowers) are marked with an 'x', while those with a '.' are marked parts of the park that are free to walk across. Spots marked with a 'T' are marked parts of the park where you can pass and there is also an outlet where Dragance can charge his phone. At the beginning of the conversation Dragance is at the fountain. In one minute he can walk to one of the nearest spots (east, west, north or south), or he can stay where he is. While he is talking on the phone he walks irregularly. When he begins going to the outlets, he will not make any stops. He will go straight to the outlets.

OutputProfessor Djuric does not know where Dragance was walking while they were talking and he wants to estimate the minimum and the maximum time that Dragance needs to get to the outlet where he can charge the phone and call Professor Djuric back. To the standard output in one row write two numbers, the MIN and MAX separated with space; they are the minimum and the maximum number of minutes Dragance needs to get to the nearest outlets.


Limitations:

*Numbers N and M are not bigger then 200
* K is not bigger then 500
*The number of spots with outlets is not bigger then 1000
*Char 'F' is located in exactly one input database
*The park is made so Dragance can always get to some of the outlets. There are no outlets in the part with the fountain.

Note:

If just one number MIN or MAX is correct, you will get 50% of the points for that example.



input:

5 5
3
x..xF
.x...
T..x.
x.T..
...T.


output:

2 5


Explanation:

After three minutes of conversation, Dragance will be able to get closer to some of the spots with outlets and then it will only take two minutes to get to them. It's possible for Dragance to stay at the fountain during the conversation, so he would then need five minutes to get to the nearest outlets.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.