When Roger finishes the programming competition he wants to meet up with his friends at the beach as soon as possible. His friends are currently in different parts of the city, and as soon as the competition ends they will simultaneously start moving towards the beach. Each friend can move in one of four directions: up, down, left, or right, as long as they do not move off the city map or into an occupied city section. Help Roger figure out where on the beach is the best place to meet and how long it will take him and his friends to get there.
An integer
denoting the number of test cases. For each test case, two integers
denoting the number of rows and columns of the city map. The next
lines contain exactly
characters each, with ’F’ denoting a friend (including
Roger), ’B’ a beach section, ’.’ an empty city
section, and ’#’ an occupied city section. The number of
friends on the map is always in the range
.
For each test case, three integers "X Y T" on a single line, where (X,Y) is the row and column coordinate of the beach section where the friends will meet, and T is the time it takes all friends to arrive. In case of ties, output the beach section with the smallest X coordinate; if there are still ties, output the beach section with the smallest Y coordinate. If it is impossible for all friends to meet at the beach, output "NO" on a single line.
Input
3 3 3 F#F .#. BBB 3 3 F#F #.. BBB 5 4 F.#F #.#. ..#. .##. BBBB
Output
3 2 3 NO 5 1 7