****Chef and Submatrix ( maximum submatrix xor)

Chef and Submatrix

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

Chef has a square matrix A. He would like to choose a consecutive sub-matrix of A such that value of bitwise XOR of all elements in it is maximal.

Each sub-matrix can be defined by four numbers (x₁,y₁,x₂,y₂), with the meaning that the submatrix contains an element A[i][j] iff x₁ ≤ i ≤ x₂ and y₁ ≤ j ≤ y₂.

You can read more about bitwise XOR operation here.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the size of the matrix A.

The following N lines contain N space-separated integers, denoting values of elements in given matrix. The j-th element in the i-th line denotes the value of A[i][j].

Output

For each test case, output a single line containing the maximal bitwise XOR a submatrix of A

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 70
• 1 ≤ A_i,j ≤ 10⁹
• Subtask 1 (40 points): 1 ≤ N ≤ 20
• Subtask 2 (60 points): 1 ≤ N ≤ 70

Example

Input:
1
3
1 4 3
1 8 6
1 2 3

Output:
15

Explanation

Chef can pick the following submatrix in order to make the XOR of elements equal to 15:

1 4 3
1 8 6
1 2 3

This submatrix can be defined by x₁ = 1, y₁ = 1, x₂ = 3, y2 = 2.

==========================================editorial=======================================

DIFFICULTY:

Easy

PREREQUISITES:

bits, implementation

PROBLEM:

You are given a square matrix A$A$ of size N$N$. For a submatrix B$B$ of A$A$, we define its value as the bitwise XOR$XOR$ of all elements of B$B$. Your task is to find the maximum value among all submatrices of A$A$.

QUICK EXPLANATION:

Since N≤70$N\le 70$, if we are able to compute a value for a given submatrix in constant time, we can iterate over all submatrices and return the maximum value. In order to compute the value for a given submatrix fast, we first compute values of all submatrices which have the upper-left corner at (1,1)$(1,1)$. Then we can use these values to compute every other value using properties of XOR$XOR$ operation.

EXPLANATION:

Let C[i][j]$C[i][j]$ be the value of the submatrix which has its upper left corner at (1,1)$(1,1)$ and its bottom right corner in (i,j)$(i,j)$. We can compute the C$C$ table in O(N4)$O(N^4)$ or O(N3)$O(N^3)$, or even O(N2)$O(N^2)$, but since N$N$ is quite small, it does not matter which method you choose.

After that, we notice the major property of XOR$XOR$, i.e. x⊕x=0$x\oplus x=0$. Using this property and precomputed table C$C$, we can easily compute the value for any submatrix R$R$ in constant time. Let's consider the below illustration and define 5 submatrices:

1. R$R$, the Red submatrix, we are interested in computing its value
2. B$B$, the Blue submatrix, we have its value computed and stored in C$C$ table
3. G$G$, the Green submatrix, we have its value computed and stored in C$C$ table
4. Y$Y$, the Yellow submatrix, we have its value computed and stored in C$C$ table
5. P$P$, the Purple submatrix, we have its value computed and stored in C$C$ table

Let's define, for the above matrices, CX$C_X$ to be the value from C$C$ table for a submatrix X$X$, for example CR$C_R$ is the value of the matrix R$R$. Then CR=CB⊕CG⊕CY⊕CP$C_R=C_B\oplus C_G\oplus C_Y\oplus C_P$

This is duo to the major property of XOR$XOR$ and the fact that both CG$C_G$ and CY$C_Y$ contain CP$C_P$ as a submatrix.

Time complexity

For a single test case it is O(N4)$O(N^4)$ because we can compute the C$C$ table in O(N4)$O(N^4)$; and we compute the value for every submatrix in a constant time, and there are O(N4)$O(N^4)$ different submatrices.

=============================code========================

1. #include<iostream>
2. using namespace std;
3. typedef long long int lli;
4. lli arr[100][100];
5. int main()
6. {
7. int t;
8. cin>>t;
9. while(t--)
10. {
13. int n;
14. cin>>n;
16. for(int i=1;i<=n;i++)
17. {
18. for(int j=1;j<=n;j++)
19. {
20. cin>>arr[i][j];
21. arr[i][j]^=arr[i-1][j]^arr[i][j-1]^arr[i-1][j-1];
22. }
23. }
26. lli ans=0;
27. for(int i=1;i<=n;i++)
28. {
29. for(int j=1;j<=n;j++)
30. {
31. for(int k=1;k<=n;k++)
32. {
33. for(int l=1;l<=n;l++)
34. {
36. lli com=arr[k][l]^arr[i-1][j-1]^arr[i-1][l]^arr[k][j-1];
38. if(com>ans) ans=com;
39. }
40. }
41. }
42. }
43. cout<<ans<<endl;
44. }
45. }