Medium Search Techniques > Ternary Search

There is a n*m Grid. You're to make k cut. - Your cut should not divide any unit square of grid. means a cut must go through the edges of unit square. - A cut must be parallel to the row or column of the grid after each cut your grid must be divided into two part. you can keep any of them and discard another. then you'll continue cutting until k cut is completed. what is the maximum possible area of remaining grid after k cut? Input: ------ 1st line of input contain a integer **T (1<=T<=10<sup>5</sup>)** , denotes the number of test case. then each of next t line contain 3 integer n,m,k **(1<=n,m,k<=10<sup>9</sup>)** Output: ------- If k cut is possible, Print 3 integer (a,x,y),separated by space for each test case in a line. a is the maximum possible area of the rectangle after k cut. , x is number of cut you make parallel to the row,y is number of cut you make parallel to the column, - x+y should be equal to k - if multiple answer is possible print that one for which x is minimum if its not possible to make k cut , then print -1 Sample Input ------------ 10 3 10 1 10 3 1 4 5 4 5 4 4 10 20 50 20 10 5 5 5 23 100 578 250 350 470 80 25 25 23 Sample Output ------------- 27 0 1 27 1 0 6 1 3 6 2 2 -1 150 5 0 -1 32800 0 250 136500 0 80 182 11 12

Md. Tariqul Islam