背景

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

题目描述

$\mathrm{NAND}$（与非）是一种二元逻辑运算，其运算结果为真当且仅当两个输入的布尔值不全为真。$\mathrm{NAND}$ 运算的真值表如下（$1$ 表示真，$0$ 表示假）:

两个非负整数的 $\mathrm{NAND}$ 是指将它们表示成二进制数，再在对应的二进制位进行 $\mathrm{NAND}$ 运算。由于两个二进制数的长度可能不等，因此一般约定一个最高位 $K$，使得两个数的二进制表示都不 超过 $K$ 位，不足 $K$ 位的在高位补零。给定 $N$ 个非负整数 $A_1, A_2, \cdots, A_n$ 和约定位数 $K$，利用 $\mathrm{NAND}$ 运算与括号，每个数可以使用任意次，请你求出范围 $[L,R]$ 内可以被计算出的数有多少个。

输入格式

输入文件第一行是用空格隔开的四个正整数 $N,K,L$ 和 $R$，接下来的一行是 $N$ 个非负整数 $A_1, A_2, \cdots, A_n$，其含义如上所述。

输出格式

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

3 3 1 4
3 4 5

4

提示

样例 $1$ 中，$(3 \text{ NAND } 4) \text{ NAND } (3 \text{ NAND } 5) = 1,5 \text{ NAND } 5 = 2$，$3$ 和 $4$ 直接可得。

对于 $100\%$ 的数据，满足 $K \le 60,N \le 1000,0 \le A_i \le 2^k - 1, 0 \le L \le R \le 10^{18}$。