Giải bài trực tuyến

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

Input

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].

Output

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

Example

Input:
1
3 3 3 3 1 1
1
2
3

Output:
260