SP912 MATRIX2 - Submatrix of submatrix

You are given a matrix P of N rows and M columns. It consists of integer numbers in the range \[1..100\]. We define the sum of a matrix is the sum of its elements. Your task is to find a submatrix Q (of A rows and B columns) of P and a submatrix K (of C rows and D columns) of Q so that the difference between the sum of Q and the sum of K is maximal, and submatrix K is absolutely inside matrix Q (i.e no element on matrix Q's sides is also in matrix K). Because the tests are large, we suggest a method to define matrix P: P\[i\]\[j\] = ( P\[i\]\[j-1\] \* 71 + 17 ) mod 100 + 1 . ( 1 ≤ i ≤ N , 1 ≤ j ≤ M ) With this method we only care about P\[i\]\[1\]. **Constraints** 1 ≤ N , M ≤ 1000 1 ≤ A ≤ N 1 ≤ B ≤ M 0 ≤ C ≤ A - 2 0 ≤ D ≤ B - 2

The first line of the input contains an integer t (1 ≤ t ≤ 10 ), equal to the number of testcases. Then descriptions of t testcases follow. The first line of the description contains 6 integer numbers N, M, A, B, C, D. Then N lines follow, line i contains one integer number P\[i\]\[1\].

For each test case, your program should output the maximal difference between two matrices (in a separate line).