## 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

### 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 3Output:260

Added by: | Nguyen Dinh Tu |

Date: | 2006-08-18 |

Time limit: | 0.595s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | Base on a problem in IOI 2006 . |