[HNOI2012]与非

题目背景

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

题目描述

NAND(与非)是一种二元逻辑运算,其运算结果为真当且仅当两个输入的布尔值不全为真。NAND运算的真值表如下(1表示真,0表示假): ![](https://cdn.luogu.org/upload/pic/7851.png) 两个非负整数的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]内可以被计算出的数的个数

输入输出样例

输入样例 #1

3  3 1 4
3  4 5

输出样例 #1

4

说明

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