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.

hide comments
vank: 2014-07-25 21:49:46

How many test cases are there??

Prakhar Gupta: 2014-06-30 22:01:37

too easy...

ওয়াসী (Wasi): 2014-04-02 21:36:41

A user with blank name or just a bug?
Check this out
--ans(Francky)--> It's really easy (using Ctrl-U to see source code of page), to know that this user is http://www.spoj.com/users/giorgi_1999/, and choose an empty name. There's several such users. Why? it a mystery (among some) for me.
--ওয়াসী(Wasi)->Thanks @Francky. I was curious cause I had to use page source to access that user's profile. The user-profile isn't accessible from the rank page (As the name is blank)

Last edit: 2014-04-03 09:02:56
anurag garg: 2014-03-20 04:46:39

easy.......

Mojtaba FayazBakhsh: 2013-08-07 02:21:44

If n would a larger amount it would be better; It has an O(nlg(a_i)) algorithm
using trie


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