题目描述

Karl 最近比较穷困，因此他开始限制自己伙食费花销，希望将一天的伙食费（Karl 从来不吃早餐，只吃午餐和晚餐）控制在 $[l,r]$ 元以内（当然伙食费也不能太低，毕竟健康重要）。

已知：

• 午餐有 $n$ 种选择，第 $i$ 种选择的花销为 $a_i$ 元。
• 晚餐有 $m$ 种选择，第 $i$ 种选择的花销为 $b_i$ 元。

Karl 希望每天吃的午餐晚餐组合都不一样，请问他一共有多少种组合可以选择。

输入格式

第一行四个正整数 $n,m,l,r$，依次表示午餐的选择数量、晚餐的选择数量、每日伙食费花销下界和上界。

第二行 $n$ 个正整数 $a_1,...,a_n$，依次表示午餐每种选择的价格。

第三行 $m$ 个正整数 $b_1,...,b_m$，依次表示晚餐每种选择的价格。

输出格式

一个整数表示结果。

5 6 6 13
1 2 7 9 6
1 1 3 9 6 7

18

9 13 120 180
56 64 58 34 27 74 26 91 44
45 38 41 65 55 45 87 89 1 92 101 43 65

45

数据规模与约定

【数据范围】

对于所有数据，$1 \leq n,m \leq 10^5$，$1 \leq l \leq r \leq 10^{15}$，$1 \leq a_i,b_i \leq 10^{15}$。

【样例 1 解释】

对于第一个午餐，它的价格为 $1$，可以选择价格为 $9,6,7$ 的晚餐。

对于第二个午餐，它的价格为 $2$，可以选择价格为 $9,6,7$ 的晚餐。

对于第三个午餐，它的价格为 $7$，可以选择价格为 $1,1,3,6$ 的晚餐。

对于第四个午餐，它的价格为 $9$，可以选择价格为 $1,1,3$ 的晚餐。

对于第五个午餐，它的价格为 $6$，可以选择价格为 $1,1,3,6,7$ 的晚餐。

一共 $18$ 种配餐方案。