All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Micro's House
Tag(s):

Data Structures, Medium, Trie

Problem
Editorial
Analytics

Our coder Micro, is building a new house. For that he bought a rectangular plot few days back. The plot is very big, so he decided that he will use some portion of the plot to make his house, and the rest he will use for playing cricket with his astrologer friend Mike. But Micro is very superstitious, he is not going to just randomly pick some portion to build his house. He want to maximize his good luck. For this he took help of Mike.
Mike divided the whole plot into grid of square blocks and assigned a Good Luck value to each. The size of the grid was N * M. For some unknown reasons Mike kept NM. Now he calculates the Good Luck value of a rectangular portion (rectangular sub matrix) as xor of Good Luck value of all square blocks in that rectangular portion. Help Micro in finding out the maximum Good Luck value he can achieve.

Input:
First line of a two space separated integers denoting N and M, (NM).
Following N lines contain M space separated integers denoting the Good Luck value of square blocks.

Output:
Print the maximum Good Luck value that Micro can achieve.

Constraints:
1≤N≤10000
1≤M≤20
1≤Good Luck value ≤10^8

SAMPLE INPUT
3 3
1 2 3
4 5 6
7 8 9
SAMPLE OUTPUT
15

Explanation

Xor of elements of submatrix highlighted in the image below is 15, and it is the maximum value possible.

enter image description here

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications