MINSUB - Largest Submatrix

no tags 

You are given an matrix M (consisting of nonnegative integers) and an integer K.  For any submatrix of M' of M define min(M') to be the minimum value of all the entries of M'.  Now your task is simple:  find the maximum value of min(M') where M' is a submatrix of M of area at least K (where the area of a submatrix is equal to the number of rows times the number of columns it has).

Input

The first line contains a single integer T (T ≤ 10) denoting the number of test cases, T test cases follow.  Each test case starts with a line containing three integers, R (R ≤ 1000), C (C ≤ 1000) and K (K ≤ R * C) which represent the number of rows, columns of the matrix and the parameter K.  Then follow R lines each containing C nonnegative integers, representing the elements of the matrix M.  Each element of M is ≤ 109.

Output

For each test case output two integers:  the maximum value of min(M'), where M' is a submatrix of M of area at least K, and the maximum area of a submatrix which attains the maximum value of min(M').  Output a single space between the two integers.

Example

Input:
2
2 2 2
1 1
1 1
3 3 2
1 2 3
4 5 6
7 8 9

Output:
1 4
8 2

hide comments
besteady: 2016-06-06 22:03:31

Please provide some hints !!

Last edit: 2016-06-06 22:04:33

Added by:acheron
Date:2014-09-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Based on APIO 2014 Training Session