NAND is a binary logical operation whose result is true if and only if not both of the two input boolean values are true. The truth table for the NAND operation is as follows (1 represents true, 0 represents false):
| Input A | Input B | Output C = A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The NAND of two non-negative integers is defined by representing them as binary numbers and performing the NAND operation on the corresponding binary bits. Since the lengths of the two binary numbers may differ, a maximum bit length $K$ is generally agreed upon, such that the binary representation of both numbers does not exceed $K$ bits, with leading zeros padded for numbers shorter than $K$ bits.
For example, the calculation of $12 \text{ NAND } 9$ ($K=4$) is as follows:
$$12 = (1100)_2, \quad 9 = (1001)_2$$ $$\begin{array}{cccc} & 1 & 1 & 0 & 0 \\ \text{NAND} & 1 & 0 & 0 & 1 \\ \hline & 0 & 1 & 1 & 1 \end{array}$$ $$(0111)_2 = 7$$
Thus, $12 \text{ NAND } 9$ ($K=4$) $= 7$.
It is easy to verify that the NAND operation satisfies the commutative law but does not satisfy the associative law. Therefore, when calculating the NAND of several numbers, operations within parentheses should be performed first, and in the absence of parentheses, calculations should proceed from left to right.
Given $N$ non-negative integers $A_1, A_2, \dots, A_N$ and a specified bit length $K$, using the NAND operation and parentheses (each number can be used any number of times), find how many numbers in the range $[L, R]$ can be calculated.
Input
The first line contains four positive integers $N, K, L,$ and $R$. The next line contains $N$ non-negative integers $A_1, A_2, \dots, A_N$.
It is guaranteed that for 30% of the data, $K \le 10$; for 70% of the data, $K \le 30$; and for 100% of the data, $K \le 60$ and $N \le 1000$, $0 \le A_i \le 2^K - 1$, $1 \le L \le R \le 10^{18}$.
Output
Output a single integer representing the number of values in the range $[L, R]$ that can be calculated.
Examples
Input 1
3 3 1 4 3 4 5
Output 1
4
Input 2
1 3 2 5 1
Output 2
0
Note
In Example 1, $(3 \text{ NAND } 4) \text{ NAND } (3 \text{ NAND } 5) = 1$, $5 \text{ NAND } 5 = 2$, and $3$ and $4$ can be obtained directly.
12 = (1100)2, 9 = (1001)2