XOR Sequence and Maximum Contiguous Interval

You are given a sequence of n integers and q queries. For each query, a positive integer x is given. Then, perform the following operations:

1. Update each element in the sequence by applying bitwise XOR with x, i.e. for every element a, set a = a ⊕ x.
2. From the updated sequence, consider its set of distinct elements and find the contiguous integer interval \([l, r]\) (with l and r being non-negative integers) such that every integer \(y\) with \(l \le y \le r\) appears in the set. The length of the interval is \(r-l+1\), and you must choose the interval with the maximum length. If there are multiple intervals, you may output any one of them.

Note:

• The term "interval" refers to a consecutive range of integers. For example, the interval \([1, 3]\) represents the numbers 1, 2, and 3.
• The "sequence" refers to the current sequence after all updates. Each query permanently changes the sequence.

inputFormat

The first line contains two integers n and q separated by a space.

The second line contains n integers, representing the initial sequence.

Each of the next q lines contains a single positive integer, representing the query parameter x.

outputFormat

For each query, output two non-negative integers l and r separated by a space, which represent the maximum contiguous interval \([l, r]\) such that every integer in that range appears in the current sequence after applying the XOR operation.

sample

5 3
1 3 3 5 7
2
4
3

1 1
1 1
0 0