Sakurako and an Impossible Task#390

Sakurako and an Impossible Task

2 secondes
256 mégaoctets
Hard

Sakurako aced her tests and is now ready for everything. You are not so sure about that. That is why you gave her a task:

You are given a matrix of size n\times m with integer numbers in it. You have to find the biggest rectangular submatrix of such that all numbers of that submatrix are in the range [l,r].

Sakurako struggled a lot but could not solve this task. She thinks that you gave her an impossible task. Now you are supposed to solve this task to prove her wrong.

Input

The first line consists of four integers n,m,l,r (1\le n,m,\le 9\cdot 10^6 ; n\cdot m\le 9 \cdot 10^6 ; 0\le l\le r\le 10^9).

Each of the next lines contains integer numbers denoting elements of matrix (0\le a_{i,j}\le 10^9)

Output

Output a single number: the area of the biggest rectangular submatrix in which every number is in the range [l,r].

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first test, the best choice would be to choose a rectangular submatrix which contains elements a_{4,2},a_{4,3},a_{5,2},a_{5,3}.

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that testing is going test by test, but not by blocks.

  • ( points): n,m\le 80;

  • ( points): \min(n,m)=1;

  • ( points): \min(n,m)\le 10;

  • ( points): without additional constraints.