xor-set

There are N numbers, A1, A2, A3,....,An. There are consecutive subsequence A[i]....A[j], where 1 ≤ i ≤ j ≤ N.

For example N=3, the sub-sequence may be:

A[1]

A[2]

A[3]

A[1] , A[2]

A[2], A[3]

A[1], A[2], A[3]

For every sub-sequence, apply XOR operation on all the sub-sequence and find the most frequent number.

INPUT:

First line contains a integer N, followed by N lines, each line contains a integer.

OUTPUT:

Output one line contains the most frequent number and how many times it appears. If there is multiple number that has the most frequency, choose the minimum number.

Constraints:

1 ≤ N ≤ 100000

1 ≤ A[i] ≤ 1000000000

SAMPLE INPUT
4
2
1
1
3

SAMPLE OUTPUT
1 3

Explanation

Finding the XOR in all the sub-sequences:

2 = 2

2 ^ 1 = 3

2 ^ 1 ^ 1 = 2

2 ^ 1 ^ 1 ^ 3 = 1

1 = 1

1 ^ 1 = 0

1 ^ 1 ^ 3 = 3

1 = 1

1 ^ 3 = 2

3 = 3

1, 2, 3 are all repeated three times. Since we are looking for the minimum number, 1 is the answer.

Source: hackerearth | Difficulty: HARD
Tags: Bit manipulation


Solutions: