NAND Closure Count

Given a set of N non-negative integers \(A_1, A_2, \ldots, A_N\) and a fixed bit-length \(K\), each of these numbers can be represented in binary with at most \(K\) bits (pad with leading zeros if necessary). Define the binary NAND operation \(\operatorname{NAND}(x,y)\) on two \(K\)-bit numbers as performing the logical NAND on each corresponding bit. In other words, for two bits \(a\) and \(b\), we have:

[ \operatorname{NAND}(a,b)=\begin{cases}1, & \text{if } (a,b)\neq (1,1),\ 0, & \text{if } (a,b)=(1,1).\end{cases} ]

When applied on two \(K\)-bit numbers \(x\) and \(y\), the result is computed bitwise. Note that this operation is equivalent to computing

[ \operatorname{NAND}(x,y)= (2^K-1) - (x & y), ]

where \(x \& y\) is the bitwise AND of \(x\) and \(y\), and \(2^K-1\) is a number whose \(K\) bits are all 1.

You are allowed to combine the given numbers arbitrarily many times (each number may be used any number of times) with the NAND operation (using appropriate parentheses). Let \(S\) be the set of all numbers (represented in \(K\) bits) that can be obtained in this way. Given two integers \(L\) and \(R\), your task is to count how many numbers in the closed interval \([L,R]\) are contained in \(S\).

Input Format: The first line contains four integers \(N\), \(K\), \(L\), and \(R\). The second line contains \(N\) non-negative integers \(A_1, A_2, \ldots, A_N\). It is guaranteed that all numbers (both inputs and computed values) can be represented with \(K\) bits.

Output Format: Output a single integer representing the count of numbers within \([L,R]\) that can be computed using the NAND operation as described.

inputFormat

The input consists of:

1. The first line contains four space-separated integers: \(N\) (the number of given integers), \(K\) (the maximum bit-length), \(L\) and \(R\) (the query interval bounds).
2. The second line contains \(N\) space-separated non-negative integers \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer: the number of values in the computed closure set \(S\) that fall in the interval \([L, R]\).

sample

3 3 0 7
1 2 3

7