You have n problems. You have estimated the difficulty of the i-th one as integer c_{i}. Now you want to prepare a problemset for a contest, using some of the problems you've made.

A problemset for the contest must consist of at least two problems. You think that the total difficulty of the problems of the contest must be at least l and at most r. Also, you think that the difference between difficulties of the easiest and the hardest of the chosen problems must be at least x.

Find the number of ways to choose a problemset for the contest.


-----Input-----

The first line contains four integers n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 10^9, 1 ≤ x ≤ 10^6) — the number of problems you have, the minimum and maximum value of total difficulty of the problemset and the minimum difference in difficulty between the hardest problem in the pack and the easiest one, respectively.

The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^6) — the difficulty of each problem.


-----Output-----

Print the number of ways to choose a suitable problemset for the contest. 


-----Examples-----
Input
3 5 6 1
1 2 3

Output
2

Input
4 40 50 10
10 20 30 25

Output
2

Input
5 25 35 10
10 10 20 10 20

Output
6



-----Note-----

In the first example two sets are suitable, one consisting of the second and third problem, another one consisting of all three problems.

In the second example, two sets of problems are suitable — the set of problems with difficulties 10 and 30 as well as the set of problems with difficulties 20 and 30.

In the third example any set consisting of one problem of difficulty 10 and one problem of difficulty 20 is suitable.

Difficulty: interview

Starter code:

Solutions:
aa=0
a, b, c, d = (list(map(int, input().split(' '))))

l = list(map(int, input().split(' ')))

for i in range(2**a):
    k = bin(i)[2:]
    t = 0
    k = '0' * (a-len(k)) + k
    x = []
    for j in range(a):
        if k[j] == '1':
            x.append(l[j])
            t += 1
            
    if t >= 2:
        if b <= sum(x) <= c and max(x) - min(x) >= d:
            aa+=1
print(aa)


import itertools
n, l, r, x = list(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
if len(C) > 1 : 
    for i in range(2, len(C)+1) :
        for j in itertools.combinations(C, i) :
            if l <= sum(j) <= r and max(j) - min(j) >= x : ans += 1

print(ans)


n,l,r,x = list(map(int,input().split()))
cs = list(map(int,input().split()))

def subsets(x):
    if len(x)==0:
        return [[]]
    a=subsets(x[1:])
    b=[[x[0]]+c for c in a]
    return a+b

sets = subsets(cs)

ans = 0
for s in sets:
    if len(s) < 2:
        continue
    if not (l <= sum(s) <= r):
        continue
    if max(s)-min(s) < x:
        continue
    ans += 1
print(ans)


n, l, r, x = [int(x) for x  in input().split()]
a = [int(x) for x in input().split()]
a.sort()
k = 1 << n
#print(a)
res = 0
lst = 0
for i in range(k):
    num = 0
    cnt = 0
    fst = -1
    for j in range(n):
        if ((1 << j) & i) != 0:
            num += a[j]
            cnt += 1
            if fst == -1:
                fst = j
            lst = j
            #print(1 << j, i)
    #print(num)
    if (cnt > 1) and (a[lst] - a[fst] >= x) and (num >= l) and (num <= r):
        #print(num, cnt, i)
        res += 1
print(res)


def gray(n):
    if n == 1:
        return ['0', '1']
    l1 = gray(n-1)
    l2 = reversed(l1)
    l1 = [a + '0' for a in l1]
    l2 = [a + '1' for a in l2]
    return l1+l2
n, l, r, x = list(map(int, input().split()))
a = list(map(int, input().split()))
ps = gray(n)
ans = 0
for i in ps:
    ma = -1
    mi = 10000000
    s=0; k = 0
    for j in range(n):
        if i[j] == '1':
            k += 1
            s += a[j]
            mi = min(mi, a[j])
            ma = max(ma, a[j])
    if s >= l and s <= r and ma - mi >= x and k > 1:
        ans += 1
print(ans)


#!/usr/bin/env python3

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

N, L, R, X = map(int, input().split(' '))
C = map(int, input().split(' '))

def is_ok(c):
    if len(c) < 2:
        return False
    if not (L <= sum(c) <= R):
        return False
    if max(c) - min(c) < X:
        return False
    return True

print(sum([1 for c in powerset(C) if is_ok(c)]))

def gen(k, n, p):
    if k == n:
        ans.append(p)
        return
    gen(k + 1, n, p + [1])
    gen(k + 1, n, p + [0])

n, l, r, x = list(map(int, input().split()))
m = list(map(int, input().split()))
ans = []
count = 0
gen(0, n, [])
for i in range(len(ans)):
    now = []
    for j in range(len(ans[i])):
        if ans[i][j] == 1:
            now.append(m[j])
    now.sort()
    sum = 0
    for i in now:
        sum += i
    if len(now) > 0:
        if now[-1] - now[0] >= x and sum >= l and sum <= r:
            count += 1
print(count)


from itertools import combinations
n, l, r, x = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(2, n+1):
    for c in combinations(C, i):
        s = sum(c)
        if s < l or r < s:
            continue
        if max(c) - min(c) < x:
            continue
        ans += 1
print(ans)


import math,string,itertools,fractions,heapq,collections,re,array,bisect
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

def VI(): return list(map(int,input().split()))

def main(n,l,r,x,c):
    all = []
    for i in range(1,n+1):
        com = combinations(c,i)
        for j in com:
            s = sum(j)
            if s>=l and s<=r and max(j)-min(j)>=x:
                all.append(j)
    print(len(all))

def main_input(info=0):
    n,l,r,x = VI()
    c = VI()
    main(n,l,r,x,c)

def __starting_point():
    main_input()


def test():
    n,l,r,x = 15, 1, 100000, 1
    c = list(range(15))
    main(n,l,r,x,c)

__starting_point()

def check_bits(x, n):
    total = 0
    for i in range(n):
        if x & (1 << i):
            total += 1

    return total >= 2


def check_compex(x, data, l, r, diff):
    total_c = 0
    min_c = None
    max_c = None

    for i in range(len(data)):
        if x & (1 << i):
            total_c += data[i]
            if min_c is None or min_c > data[i]:
                min_c = data[i]
            if max_c is None or max_c < data[i]:
                max_c = data[i]

    return l <= total_c <= r and max_c - min_c >= diff


def __starting_point():
    n, l, r, diff = list(map(int, input().split()))
    data = list(map(int, input().split()))

    total = 0
    for i in range(2 ** n):
        if check_bits(i, n) and check_compex(i, data, l, r, diff):
            total += 1

    print(total)

__starting_point()

def generate(made, lis):
    if made == n:
        nonlocal res
        s = sum(lis)
        if l <= s and s <= r and len(lis) >= 2 and lis[-1] - lis[0] >= x:
            res += 1
    else:
        generate(made + 1, lis + [a[made]])
        generate(made + 1, lis)

n, l, r, x = list(map(int, input().split()))
a = sorted(map(int, input().split()))
res = 0
generate(0, [])
print(res)


import itertools
n, l, r, var = (int(x) for x in input().split())
arr = list(int(x) for x in input().split())
ans = 0
for i in range(2, len(arr) + 1):
	for comb in itertools.combinations(arr, i):
		curComb = list(comb)
		if sum(curComb) <= r and sum(curComb) >= l and max(curComb) - min(curComb) >= var:
			ans += 1
print(ans)

#n = int(input())
import itertools
n, l, r, x = [int(c) for c in input().split()]
c = [int(c) for c in input().split()]

c.sort()
count = 0
for i in range(2, n + 1):
    combs = itertools.combinations(c, i)
    for comb in combs:
        min = comb[0]
        max = comb[0]
        sum = 0
        for a in comb:
            sum += a
            if a > max:
                max = a
            if a < min:
                min = a
        if sum >= l and sum <= r and max - min >= x:
            count +=1

print(count)

n, l, r, x = map(int, input().split())
a = input().split()
ran = 2**n
answer = 0
for i in range(n):
    a[i] = int(a[i])
for i in range(ran):
    m = i
    mask = ""
    while m != 0:
        if m % 2 == 0:
            mask += '0'
        else:
            mask += '1'
        m = m//2
    while len(mask)<n:
        mask += '0'
    s = 0
    easy = 10**9+100
    hard = 0
    for j in range(len(mask)):
        if mask[j] == '1':
            if a[j] >= hard:
                hard = a[j]
            if a[j] <= easy:
                easy = a[j]
            s += a[j]
    if s <= r and s >= l and hard-easy >= x:
        answer += 1

print(answer)

from itertools import *
n, l, r, x = map(lambda x: int(x), input().split())
c = sorted(list(map(lambda x: int(x), input().split())))
variants = []
for i in range(2, n + 1):
    variants.extend(list(combinations(c, i)))
counter = 0
for i in range(len(variants)):
    sum_var = sum(variants[i])
    if sum_var >= l and sum_var <= r and (variants[i][-1] - variants[i][0]) >= x:
        counter += 1
print (counter)

def generate(i, real, a):
    if i == n:
        if real >= 2:
            min_a = a[0]
            max_a = a[real-1]
            sum_a = sum(a)
            if (sum_a >= l) and (sum_a <= r) and (max_a-min_a >= x):
                count[0] += 1
    else:
        generate(i+1, real+1, a+[c[i]])  # взяли эту задачу
        generate(i+1, real, a)  # не взяли эту задачу
        
n, l, r, x = map(int, input().split())
c = sorted(list(map(int, input().split())))
count = [0]
generate(0, 0, [])
print(count[0])

from itertools import combinations

n,l,r,x = map(int, input().split())
problems = [int(x) for x in input().split()]

ans = 0
for i in range(2,n+1):
    for comb in combinations(problems, i):
        isum = sum(comb)
        imin = min(comb)
        imax = max(comb)
        if l <= isum <= r and imax-imin >= x:
            ans += 1

print(ans)

import itertools

n, l, r, x = input().split()
n = int(n)
l = int(l)
r = int(r)
x = int(x)
numbers = [int(z) for z in input().split()]
numbers = sorted(numbers)
count = 0;
for z in range(2, len(numbers)+1):
    for subset in itertools.combinations(numbers, z):
        total = sum(subset)
        if total >= l and total <= r and subset[-1]-subset[0] >= x:
            count+=1
print(count)


def main():
    import sys
    n, l, r, x, *c = [int(i) for i in sys.stdin.read().split()]
    result = 0
    for mask in range(1 << n):
        number = 0
        minimal = float("inf")
        maximal = -float("inf")
        s = 0
        for i in range(n):
            if mask & (1 << i):
                s += c[i]
                number += 1
                minimal = min(minimal, c[i])
                maximal = max(maximal, c[i])
        if number >= 2 and l <= s <= r and maximal - minimal >= x:
            result += 1
    print(result)
    
    
main()


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def test(a, b, C, s, n, l, r, x, p):
    if C == []:
        if s >= l and s <= r and b-a >=x:
#            print("!!!!!!!!", a, b, C, s, p)
            return 1
        return 0

    if s>=l and s <= r and b-a>=x:
        acc = 1
    else:
        acc = 0

#    print(a, b, C, s, p)
    for i in range(len(C)):

        if s+C[i] <= r:
            acc += test(min(a, C[i]), max(b, C[i]), C[i+1:], s+C[i], n, l, r, x, p+[C[i]])

    return acc

import time
(n, l, r, x) = (int(i) for i in input().split())
C            = sorted([int(i) for i in input().split()])
#print(C)

start = time.time()
acc   = 0

for i in range(len(C)):
    acc += test(C[i], C[i], C[i+1:], C[i], n, l, r, x, [C[i]])

print(acc)
finish = time.time()
#print(finish - start)


from itertools import combinations


def main():
    n, l, r, x = [int(t) for t in input().split()]
    c = [int(t) for t in input().split()]

    def is_valid(candidate):
        mx = max(candidate)
        mn = min(candidate)
        sm = sum(candidate)
        return l <= sm <= r and (mx - mn) >= x

    way = 0

    for L in range(2, len(c) + 1):
        for subset in combinations(c, L):
            if is_valid(subset):
                way += 1

    print(way)

def __starting_point():
    main()
__starting_point()

import itertools

def classify(subset, l, r, x):
    li = []
    for i in subset:
        li.append(i)
    f1 = False
    f2 = False
    f3 = False
    s = 0
    for i in li:
        s += i
    if s >= l:
        f1 = True
    if s <= r:
        f2 = True
    li.sort()
    t =  li[len(li)-1] - li[0]
    if t >= x:
        f3 = True
    if f1 and f2 and f3:
        return True
    else:
        return False

s = input()
s = s.split()
n = int(s[0])
l = int(s[1])
r = int(s[2])
x = int(s[3])

a = input()
a = a.split()
arr = []
for i in a:
    arr.append(int(i))

count  = 0
for i in range(2, len(arr)+1):
    for subset in itertools.combinations(arr, i):
        #print(subset)
        if classify(subset, l, r, x):
            #print(subset)
            count += 1

print(count)


n, l, r, x = [int(y) for y in input().split()]
c = [int(y) for y in input().split()]
c.sort()
ans = [0]

def solve(ans, tasklist = [], e = 0):
    if sum(tasklist) <= r and sum(tasklist) >= l and len(tasklist) >= 2 and max(tasklist) - min(tasklist) >= x:
        ans[0] += 1
    for i in range(e, n):
        tasklist.append(c[i])
        solve(ans, tasklist, i + 1)
        del tasklist[len(tasklist) - 1]

solve(ans)
print(ans[0])


def f(k, n, ma, mi, sum):
    if k:
        if sum + k[0] <= r and sum + k[0] >= l and   max(k[0], ma) - min(k[0], mi) >= x:
            n+=1
        if sum <= r:
            n = f(k[1:], n, ma, mi, sum)
            n = f(k[1:], n, max(k[0], ma), min(k[0], mi), sum + k[0])
    return n
n, l, r, x = [int(i) for i  in input().split()]
s = [int(i) for i  in input().split()]
n = f(s, 0, 0, 10**9, 0)
print(n)