Monk's Step Challenge

In ancient funeral rites it was common to invite eminent monks to perform ceremonies. After the main ritual, sometimes a fun event called Monk Duel was organized to relieve the oppressive atmosphere.

The program proceeds roughly as follows: Using food grains (usually rice), several levels of steps are "drawn" on the ground to represent a pagoda of $N$ levels. A number of young monks then randomly stand on some of these steps, with the highest step always occupied and any other step possibly occupied. (See Figure 1.)

During the game, two competing masters take turns issuing commands. On a turn, a master chooses one monk and instructs him to move upward by any positive number of steps. However, the monk cannot move past any other monk already standing on a higher step and he cannot land on a step already occupied by another monk. In addition, movements toward lower steps are not allowed.

The game eventually reaches a state where all monks are crowded at high-level steps and no one can move further upward. The player whose turn it is when no legal move exists loses the game. Given the number of steps and the initial positions of the monks, your task is to compute the winning decision (i.e. the move to make) for the first master, if one exists.

Game Analysis: Number the steps from 1 to $N$, where the top step is $N$. Let the positions of the $M$ monks be sorted in increasing order: $p_1, p_2, \dots, p_M$ with $p_M=N$. For each consecutive pair, define the gap as $$d_i=p_{i+1}-p_i-1.$$ A legal move is to pick a monk at position $p_i$ (where $1\le i0$) and move it upward by any number $t$ ($1\le t\le d_i$). This reduces the gap to \(d_i-t\). It turns out that this game is equivalent to a Nim game where each gap is a pile with size $d_i$. The Grundy number for each pile is just its size, and a move corresponds to subtracting a positive number from that pile. Therefore, the winning condition is determined by the nim-sum (bitwise XOR) of all gap sizes. The first master has a winning move if and only if the nim-sum is nonzero.

If the overall nim-sum is nonzero, one can always find an index $i$ for which \(d_i \oplus G < d_i\) holds (where $G$ is the nim-sum and \(\oplus\) denotes bitwise XOR). By moving the monk at position $p_i$ upward by $$t = d_i - (d_i \oplus G),$$ the configuration is changed so that the nim-sum becomes zero, thus ensuring a winning strategy. Otherwise, if the nim-sum is zero, there is no winning move.

inputFormat

The input consists of two lines.

The first line contains two integers $N$ and $M$ ($1 \le M \le N \le 10^9$), where $N$ is the number of steps and $M$ is the number of monks. Note that the top step (step $N$) is always occupied.

The second line contains $M$ integers representing the positions of the monks. The positions may be given in any order, and they are guaranteed to be distinct.

outputFormat

If there is a winning move, output two integers separated by a space: the current step of the monk to move and the step he should move to. If there is no winning move (i.e. the nim-sum is zero), output 0 0.

sample

10 3
2 7 10

2 4