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\).