Alice is playing another game called BOOM. The game has a rectangular map of size N ×M. Each 1×1 cell is a wall, an enemy, or an empty cell. In this game, a bomb has a horizontal explosion range with radius V . In other words, if the bomb is placed at cell (i, j), its explosion range is from the cell (i, j − V ) to the cell (i, j + V ). It is not allowed to place bombs at the wall cells, it is allowed to place bombs in the remaining cells. The bomb explodes at its placed cell and spreads to both horizontal sides, until it reaches the end of its explosion range or encounters a wall. Note that the wall will not be destroyed by bombs. In this game, Alice will carry exactly K bombs. Therefore, before entering the map, Alice must buy K bombs with an explosion range of V . To save in-game money, Alice will buy exactly K bombs with the minimum V but can still destroy all enemies in the map. Please help Alice to calculate the minimum V . Input The first line contains three positive integers N, M, K safety N × M, K ≤ 10^5 In the next N lines, each line contains M characters of the following characters: ’#’ is a wall, ’.’ is an empty cell, ’x’ is an enemy. Output Output the minimum V so that Alice can place K bombs to destroy all enemies. If there is no answer, output −1. Example1: input: 4 6 5

x..#.

.x.x

..#.xx x....x output: 1 Example 2: Input: 2 3 10 xxx xxx Output: 0 Example 3: Input: 2 2 1 x. x. Output: -1 Test case 1: With V = 1, she can place 5 bombs in cells: (1, 2),(2, 4),(3, 5),(4, 1),(4, 6). This is the minimum V . Test case 2: She can place bombs in all cells in the map. Test case 3: She cannot destroy all enemies with 1 bomb