The $\textit{score}$ of a sequence that contains positive integers $b_1, b_2, \ldots, b_k$ is given as $\mathrm{gcd}(b_1, b_2, \ldots, b_k)$.

You are provided a sequence of positive integers $a_1, a_2, \ldots, a_n$ and two integers $l$ and $r$ $(l \le r)$. You are required to select an integer $x\ (l \le x \le r)$ and add $x$ to all elements of the $a$. This provides you a new sequence of positive integers$a_1 + x, a_2 + x, \ldots, a_n + x$.

If you have selected the $x$ through an optimal way, then determine the maximum score of $a_1 + x,\ a_2 + x,\ \ldots, a_n + x$?

Input format

• First line: Three integers $n,\ l,\ and\ r$ representing the number of elements available in the $a$ sequence and the allowed range of $x$ $(1 \leq n \leq 10^6,\ 1 \leq l \leq r \leq 10^{12})$
• Second line: $a_1, a_2, \ldots, a_n\ (1 \leq a_i \leq 10^{12})$

Output format

Print an integer that represents the maximum score of $a_1 + x, a_2 + x, \ldots, a_n + x$.