Or
Consider a positive integer X and an N by N matrix A with positive integer entries. Determine the minimum area of a continuous submatrix for which the bitwise or of all its elements equals X.
Input
The input contains on the first line integers X and N (2 ≤ N ≤ 500), separated by a space. On the following N lines there are N positive integers separated by spaces representing a matrix line (1 ≤ A[i][j] < 231).
Output
The output will contain a positive integer representing the minimum area of the submatrix. It is guaranteed that for all input data there will always be a solution and the minimum area will be at least 2.
The bitwise or of two positive integers is the integer whose i-th bit equals 0 if and only if the i-th bit of both integers is 0.
Constraints
Time limit: 2 seconds
Memory limit: 128 megabytes
Examples
input 11 4 5 9 1 8 7 7 3 1 2 3 1 9 5 5 8 7 | output 3 |
The submatrix is the highlighted one
(3 | 1 | 9 = 11)
5 9 1 8
7 7 3 1
2 3 1 9
5 5 8 7