F. Another Bitwise Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. How many numbers between $$$l$$$ and $$$r$$$ can be expressed in the form $$$\displaystyle\sum_{i=1}^{n} (a_i \oplus x)$$$, where $$$x$$$ is a nonnegative integer, and $$$\oplus$$$ denotes the bitwise XOR operation?

Input

The first line consists of three integers $$$n$$$, $$$l$$$, and $$$r$$$ $$$(1 \leq n \leq 10^{5}, 0 \le l \le r \le 10^{18})$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^5)$$$.

—

The first $$$5$$$ test cases (not including the sample) satisfy $$$n \le 100$$$, $$$a_i \le 100$$$, $$$0 \le l \le r \le 10^5$$$.

Output

Print a single integer $$$-$$$ the number of reachable integers in the range $$$[l, r]$$$.

Example
Input
3 0 12
1 2 3
Output
4
Note

$$$x = 0$$$ gives a sum of $$$6$$$.

$$$x = 1$$$ gives a sum of $$$5$$$.

$$$x = 2$$$ gives a sum of $$$4$$$.

$$$x = 3$$$ gives a sum of $$$3$$$.

—

Problem Idea: thehunterjames

Problem Preparation: thehunterjames

Occurrences: Novice 9, Advanced 6