On a M*N grid land, Mr. Mumu wants to find a largest square-shaped area to build his own guitar placing area. But there are some dust occupies the some of the 1*1 unit squares. Mr. Mumu wants to keep his guitar clean, so he does not want to find any place contain more than k dust squares. Please help him to find the most suitable position to build Mumu's area. Note that this area must be square-shaped, and its side must attach to the grid lines (horizontal or vertical grid lines) of the land.
The first line of the input file contains an integer denoting the number of test cases. For each test case, the first line contain three positive integers M, N, k (M, N<= 1000, and 0<=k<=M*N). Each of the next M lines contains a binary string of length N indicating the status of each corresponding unit square: '1' with dust inside, '0' without dust. There are at most 50 test cases. You may assume there are at least one zero appearing in each test case.
For each test case, please output a line contains three integers, X, Y, n. Where (X,Y) denotes the X-th line's Y-th character, which means the left-topmost position of the larget valid square. If there are more than one positions, please choose minimum X among all positions. If there is still a tie, please select one with minimum Y. Moreover, n is the size of the square for Mumu.
3 5 5 0 10000 00001 10001 11000 11000 5 5 2 10000 00001 10001 11000 11000 5 5 3 10000 00001 10001 11000 11000
1 2 3 1 1 3 1 2 4
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|