[HNOI2012] 与非

如果你能提供题面或者题意简述，请直接在讨论区发帖，感谢你的贡献。

NAND（与非）是一种二元逻辑运算，其运算结果为真当且仅当两个输入的布尔值不全为真。NAND运算的真值表如下（1表示真，0表示假）:  两个非负整数的NAND是指将它们表示成二进制数，再在对应的二进制位进行NAND运算。由于两个二进制数的长度可能不等，因此一般约定一个最高位K，使得两个数的二进制表示都不 超过K位，不足K位的在高位补零。给定N个非负整数A1,A2......AN和约定位数K，利用NAND运算与括号，每个数可以使用任意次，请你求出范围[L,R]内可以被计算出的数有多少个。

输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2......AN，其含义如上所述。 100%的数据满足K<=60且N<=1000,0<=Ai<=2^k-1,0<=L<=R<=10^18

仅包含一个整数，表示[L,R]内可以被计算出的数的个数

3  3 1 4
3  4 5

4

样例1中，(3 NAND 4) NAND (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。