#include <cstdio>
#define int long long
const int M = 1005; 
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,l,r,a[M],b[M],sum[M];
int ask(int x)
{
	if(x<0) return -1;
	if(x>(1ll<<m)-1) return (1ll<<sum[m-1])-1;
	int res=0,s=0;
	for(int i=m-1;i>=0;i--) if(x>>i&1)
	{
		//0
		if(i && !(s>>i&1))
			res+=(1ll<<sum[i-1])-1;
		//1
		if(b[i])//Meanwhile s>>i&1==0
		{
			s|=b[i];
			if(s>x) break;
			res++;
		}
		else if(!(s>>i&1)) break;
	}
	return res;
}
signed main()
{
	n=read();m=read();l=read();r=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=m-1,s=0;i>=0;i--)
		if(!(s>>i&1))
		{
			int &now=b[i];now=(1ll<<m)-1;
			for(int j=1;j<=n;j++)
				if(a[j]>>i&1) now&=a[j];
				else now&=~a[j];
			sum[i]=1;s|=now;
		}
	for(int i=1;i<m;i++) sum[i]+=sum[i-1];
	printf("%lld\n",ask(r)-ask(l-1));
}