QN01 - XOR Game

You are given an array of n integers (0 <= n <= 1000). Find a contiguous subsequence of these numbers [ai, aj] (1 <= i, j <= n), such that the Exclusive-OR of these numbers is maximum. (That is, ai XOR ai+1 XOR ... aj should be maximum).

Input

The test case contains exactly 2 lines of input.

The first line contains a single integer n (0 <= n <= 1000), the total number of integers in the sequence given to you.

The next line contains n space separated integers such that the ith integer denotes ai. (0 <= ai <= 109). Note that these integers need not necessarily be distinct.

Output

Output two lines. In the first line, print out the value of the maximum XOR.

In the second line, print out i and j with a space separating them, such that [ai, aj] (both endpoints inclusive) denotes the contiguous subsequence with the maximum XOR value.

In case there is more than one subsequence with the maximum XOR value, print out the pair (i, j) such that (i, j) is lexicographically smallest. (Formally, we say that a pair (a, b) is lexicographically smaller than another pair (c, d) if and only if (i) a < c or (ii) a=c and b < d.)

NOTE : The subsequence must be non-empty, but may be allowed to contain just one integer. (i.e, in this case, i = j)

Example

Input #1:
1
4

Output #1:
4
1 1
Input #2:
3
1 2 3

Output #2:
3
1 2

Explanation

  1. In the first test case, since there is only one number, the maximum XOR would be simply the value of that number (in this case, 4), and i = j = 1.
  2. In the second test case, the maximum XOR value is 3, but there are 2 contiguous subsequences that define the same XOR value - (i) [1, 2] since 1 XOR 2 = 3 (ii) [3, 3] since this subsequence contains just the single integer 3. But since [1, 2] is lexicographically smaller than [3, 3], [1, 2] is the desired output.

Added by:Gowri Sundaram
Date:2012-11-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-07-15 18:30:36
SAME PROBLEM WITH BETTER CONSTRAINTS : https://icpcarchive.ecs.baylor.edu/index.php?Itemid=8&category=345&option=com_onlinejudge&page=show_problem&problem=2683
2017-02-14 11:23:27
easy one..
2017-01-25 12:19:32
AC in one go. Didn't expect that.

Last edit: 2017-01-25 12:21:58
2017-01-25 12:19:31
O(n^2) passes.... that too with 0.0 s
2016-09-09 20:35:42 Sarthak Munshi
lol . O(n^2) passes !
2016-06-23 11:31:42
Just trie !! ;) 0.0sec

Last edit: 2016-07-05 18:30:24
2016-06-01 23:24:07
better use "trie" than the brute force approach....
2016-01-18 13:06:10 epsilon
poor test cases !!! wondering how O(n^2) got accepted
2015-06-28 03:47:01 thirupathireddy
what is O(nlogn) algorithm.......?
2014-08-05 22:03:27 psyclaudeZ
...Why would I use long long
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.