Little X and Little Z are good friends. They always chat online. But both of them have schedules.

Little Z has fixed schedule. He always online at any moment of time between a_1 and b_1, between a_2 and b_2, ..., between a_{p} and b_{p} (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time 0, he will be online at any moment of time between c_1 and d_1, between c_2 and d_2, ..., between c_{q} and d_{q} (all borders inclusive). But if he gets up at time t, these segments will be shifted by t. They become [c_{i} + t, d_{i} + t] (for all i).

If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between l and r (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment [l, r] suit for that?


-----Input-----

The first line contains four space-separated integers p, q, l, r (1 ≤  p, q ≤ 50; 0 ≤ l ≤ r ≤ 1000).

Each of the next p lines contains two space-separated integers a_{i}, b_{i} (0 ≤ a_{i} < b_{i} ≤ 1000). Each of the next q lines contains two space-separated integers c_{j}, d_{j} (0 ≤ c_{j} < d_{j} ≤ 1000).

It's guaranteed that b_{i} < a_{i} + 1 and d_{j} < c_{j} + 1 for all valid i and j.


-----Output-----

Output a single integer — the number of moments of time from the segment [l, r] which suit for online conversation.


-----Examples-----
Input
1 1 0 4
2 3
0 1

Output
3

Input
2 3 0 20
15 17
23 26
1 4
7 11
15 17

Output
20

Difficulty: interview

Starter code:

Solutions:
__author__ = 'sonerik'

import sys

inp = sys.stdin
# inp = open("a.txt")

p, q, l, r = map(int, inp.readline().strip().split())

z, x = [], []

for i in range(p):
    a_i, b_i = map(int, inp.readline().strip().split())
    z += [i for i in range(a_i, b_i+1)]

z_set = set(z)

for i in range(q):
    c_i, d_i = map(int, inp.readline().strip().split())
    x += [i for i in range(c_i, d_i+1)]

cnt = 0

for i in range(l, r+1):
    new_x = [j + i for j in x]
    new_x_set = set(new_x)
    if new_x_set.intersection(z_set):
        cnt += 1

print(cnt)

p, q, l, r = list(map(int, input().split()))
a = [0] * p
b = [0] * p
c = [0] * q
d = [0] * q
for i in range(p):
    a[i], b[i] = list(map(int, input().split()))
for i in range(q):
    c[i], d[i] = list(map(int, input().split()))
cnt = 0
for t in range(l, r + 1):
    events = \
        list([(x + 0, +1) for x in a]) + \
        list([(x + 0, -1) for x in b]) + \
        list([(x + t, +1) for x in c]) + \
        list([(x + t, -1) for x in d])
    events.sort(key=lambda x: (x[0], -x[1]))
    online = 0
    for _, i in events:
        online += i
        if online > 1:
            cnt += 1
            break
print(cnt)


p,q,x,y = list(map(int, input().split()))
a = [0 for i in range(p)]
b = [0 for i in range(p)]
c = [0 for i in range(q)]
d = [0 for i in range(q)]
for i in range(p):
    a[i], b[i] = list(map(int, input().split()))
for i in range(q):
    c[i], d[i] = list(map(int, input().split()))


ans = 0

def comp(k,l,m,n):
    if m <= l and k <= n:
        return 0 #eq
    elif m >= l:
        return 1 #ab<cd
    else:
        return -1 #ab>cd

for t in range(x, y+1):
    i = 0
    j = 0
    while i < p and j < q:
##        print('i = ',i,'; j = ',j)
        z = comp(a[i], b[i], c[j] + t, d[j] + t)
##        print('comp(', a[i],',',b[i],',',c[j]+t,',',d[j]+t,') = ',z)
        
        if z == 0:
            ans += 1
            break
        elif z == 1:
            i += 1
        else:
            j += 1

print(ans)
    
    


t=list(input().split())
p=int(t[0])
q=int(t[1])
l=int(t[2])
r=int(t[3])
xv=list()
zv=list()
for i in range(p):
    t=list(int(x) for x in input().split())
    zv+=list(x for x in range(t[0],t[1]+1))
sv=set(zv)
#print (sv)

for i in range(q):
    t=list(int(x) for x in input().split())
    xv+=list(x for x in range(t[0],t[1]+1))
#print (xv)

c=0
for i in range (l, r+1):
    for j in range (q):
        tt=set((x+i) for x in xv)
        if (tt&sv)!=set():
            c+=1
            break       

# for i in range (q):
    # t=list(int(x) for x in input().split())
    # for k in range (l,r+1):
        # tt=set((x+k) for x in range (t[0],t[1]+1))
        # print (tt)
        # if (tt&sv)!=set():
            # c+=1
            # break
print (c)


def inter(A, B, t):
    for i in B:
        if (i + t) in A:
            return True
    return False


p, q, r, l = list(map(int, input().split()))
X = set()
Z = set()
for i in range(p):
    b, e = list(map(int, input().split()))
    for i in range(b, e + 1):
        Z.add(i)
for i in range(q):
    b, e = list(map(int, input().split()))
    for i in range(b, e + 1):
        X.add(i) 
cnt = 0
for i in range(r, l + 1):
    if inter(Z, X, i):
        cnt += 1
print(cnt)
    


x1=[]
x2=[]
p, q, l, r = list(map(int, input().split(' ')))
for i in range(p):
    a, b = list(map(int, input().split(' ')))
    x1.append([a, b])

for i in range(q):
    a, b = list(map(int, input().split(' ')))
    x2.append([a, b])

ok2 = []

for a in x1:
    for b in x2:
        lo = a[0]-b[1]
        hi = a[1]-b[0]
        if hi >= r:
            hi = r
        if lo <= l:
            lo = l
        ok2.append([lo, hi])

ok = [i for i in ok2 if i[1]>=i[0]]
ok.sort()
total = 0
if len(ok)==0:
    print(0)
else: 
    intv = ok[0]
    for i in range(1, len(ok)):
        curr = ok[i]
        if curr[0] > intv[1]:
            if intv[1] == intv[0]:
                total += 1
            else:
                total += intv[1]-intv[0]+1
            intv = curr
        else:
            minim = [min(curr[0], intv[0]), max(curr[1], intv[1])]
            intv = minim

    if intv[1] == intv[0]:
        total += 1
    else:
        total += intv[1]-intv[0]+1
    print(total)


p, q, l, r = map(int, input().split())
arr_z = [0] * (p * 2)
i = 0
for k in range(p):
    t = list(map(int, input().split()))
    arr_z[i], arr_z[i + 1] = (t[0], -1), (t[1], 1)
    i += 2
arr_z.sort()
arr = [False] * 1001
for i in range(q):
    t = list(map(int, input().split()))
    t[1] = t[1] - t[0]    
    f = t[0]
    for j in range(l, r + 1):
        t[0] = f + j
        if arr[j] != True:
            tl = -1
            tr = (p * 2)
            while tr > tl + 1:
                m = (tr + tl) // 2
                if t[0] < arr_z[m][0]:
                    tr = m
                elif t[0] > arr_z[m][0]:
                    tl = m
                else:
                    if arr_z[m][1] == 1:
                        tr = m
                    else:
                        tl = m
            if (tr < p * 2 and arr_z[tr][0] <= t[0] + t[1]) or (tr != 0 and arr_z[tr - 1][1] == -1):
                arr[j] = True
ans = 0
for i in arr[l:r + 1]:
    if i == True:
        ans += 1
print(ans)

#!/usr/bin/env python3
from sys import stdin
p, q, l, r = map(int, stdin.readline().split())

z_list = []
x_list = []
for x in range(p):
	i, j = map(int, stdin.readline().split())
	for x in range(i, j+1):
		z_list.append(x)
for x in range(q):
	i, j = map(int, stdin.readline().split())
	for x in range(i, j+1):
		x_list.append(x)

t = l
ans = 0
for x in range(l, r+1):
	xt_list = [x+t for x in x_list]
	t += 1
	if len(list(set(z_list) & set(xt_list))) != 0:
		ans += 1

print(ans)

def read_to_list(count):
    s = []
    for i in range(count):
        start, stop = [int(i) for i in input().split()]
        s.extend(list(range(start, stop + 1)))
    return s


def has_equal_items(first, second):
    for item in first:
        if item in second:
            return True
    return False


def update_list(l, t):
    for i in range(len(l)):
        l[i] += t

def main():
    p, q, l, r = [int(i) for i in input().split()]
    z, x = read_to_list(p), read_to_list(q)
    if l > 0:
        update_list(x, l)
    count = 1 if has_equal_items(z, x) else 0
    for t in range(l, r):
        update_list(x, 1)
        if has_equal_items(x, z):
            count += 1
    print(count)


def __starting_point():
    main()


__starting_point()

p, q, l, r = list(map(int, input().split()))
x = [0] * 10000
y = []
cnt = 0
for i in range(p):
    a, b = list(map(int, input().split()))
    for j in range(a, b + 1):
        x[j] = 1
for i in range(q):
    a, b = list(map(int, input().split()))
    y.append((a, b))
    
for i in range(l, r + 1):
    f = 0
    for j in range(q):
        if not f:
            for k in range(y[j][0] + i, y[j][1] + i + 1):
                if x[k]:
                    f = 1
                    break
        else:
            break
    cnt += f
print(cnt)
    
    


def main():
    p, q, l, r = list(map(int, input().split()))
    Z = set()
    X = []

    for _ in range(p):
        ai, bi = list(map(int, input().split()))
        Z.update(list(range(ai, bi+1)))
    for _ in range(q):
        ai, bi = list(map(int, input().split()))
        X.extend(list(range(ai, bi+1)))

    res = 0
    for i in range(l, r+1):
        for j in X:
            if j + i in Z:
                res += 1
                break
    print(res)


def __starting_point():
    main()


__starting_point()

p, q, l, r = map(int, input().split())

mySet1 = set()
mySet2 = set()

for i in range(p):
    a, b = map(int, input().split())
    for i in range(a, b+1):
        mySet1.add(i)


for i in range(q):
    a, b = map(int, input().split())
    for i in range(a, b+1):
        mySet2.add(i)


m = max(mySet1)
cnt = 0

for t in range(l, r+1):
    for item in mySet2:
        if t+item in mySet1:
            cnt +=1
            break

print(cnt)

p,q,l,r = tuple(map(int, input().split(' ')))
IP = [False]*1001
IQ = [False]*1001
for i in range(p):
    a,b = tuple(map(int, input().split(' ')))
    IP[a:b+1] = [True]*(b-a+1)
  
for i in range(q):
    a,b = tuple(map(int, input().split(' ')))
    IQ[a:b+1]=[True]*(b-a+1)

li = []
li= [1 for i in range(l,r+1) if any([True for j in range(1001-i) if IP[i+j] and IQ[j] ]) ]

print(sum(li))
     



p,q,l,r = tuple(map(int, input().split(' ')))
IP = [False]*1001
IQ = [False]*1001
for i in range(p):
    a,b = tuple(map(int, input().split(' ')))
    IP[a:b+1] = [True]*(b-a+1)
  
for i in range(q):
    a,b = tuple(map(int, input().split(' ')))
    IQ[a:b+1]=[True]*(b-a+1)

li = []
li= (1 for i in range(l,r+1) if any(True for j in range(1001-i) if IP[i+j] and IQ[j] ) )

print(sum(li))

p,q,l,r=list(map(int,input().split(' ')))
plist=list()
qlist=list()
for i in range(p):
    plist.append(list( map(int,input().split()) ))
for i in range(q):
    qlist.append(list( map(int,input().split()) ))

pset=set()
qset=set()
for j in range(p):
    pset=pset | set(range( plist[j][0], plist[j][1]+1 ) )

whengetup=0
for i in range(l,r+1):
    qset=set()
    for j in range(q):
        qset=qset | set(range( qlist[j][0]+i, qlist[j][1]+i+1 ) )
    if len(pset & qset)>0:
        whengetup+=1

print(whengetup)


def f (x1, y1, x2, y2):
    return x1 <= x2 <= y1 or x1 <= y2 <= y1 or x2 <= x1 <= y2

p, q, l, r = list(map(int, input().split()))
a1, a2 = [(0, 0)] * p, [(0, 0)] * q
for i in range(p):
    a, b = list(map(int, input().split()))
    a1[i] = (a, b)
for i in range(q):
    a, b = list(map(int, input().split()))
    a2[i] = (a, b)
res = [False] * 2000
ans = 0
for i in a1:
    for j in a2:
        for k in range(max(0, i[0] - j[1]), i[1] - j[0] + 1):
            res[k] = True
for i in range(l, r + 1):
    if res[i]:
        ans += 1
print(ans)


p, q, l, r = map(int, input().split())
t = [0] * 1002
z = [list(map(int, input().split())) for i in range(p)]
x = [list(map(int, input().split())) for i in range(q)]
for xl, xr in x:
    for zl, zr in z:
        a, b = zl - xr, zr - xl + 1
        if b <= l: continue
        if a > r: break
        if a < l: a = l - 1
        if b <= r: t[b] -= 1
        t[a] += 1
for i in range(l, r + 1): t[i] += t[i - 1]
print(r - l + 1 - t[l: r + 1].count(0))

#Codeforces 469B
#Chat Online

p,q,l,r=input().split()
fixed=[]
for i in range(int(p)):
    endpoints=input().split()
    for j in range(int(endpoints[0]),int(endpoints[1])+1):
        fixed+=[j]

temp=[]
for i in range(int(q)):
    endpoints=input().split()
    for j in range(int(endpoints[0]),int(endpoints[1])+1):
        temp+=[j]

count=0
for time in range(int(l),int(r)+1):
    new_temp=temp[:]
    new_temp=[i+time for i in new_temp]
    for i in new_temp:
        if i in fixed:
            count+=1
            break

print(count)


p,q,l,r = list(map(int, input().split(' ')))
P = []
Q = []
for i in range(p) :
    P.append(list(map(int, input().split(' '))))
for i in range(q) :
    Q.append(list(map(int, input().split(' '))))
res = 0
for i in range(l, r+1) :
    index_q = 0
    index_p = 0
    for j in range(p+q) :
        if index_q == q or index_p == p : break
        if P[index_p][1] < Q[index_q][0] + i :
            index_p += 1
        elif Q[index_q][1] + i< P[index_p][0] :
            index_q += 1
        else :
            res += 1
            break
print(res)
        


RMAX = 1000
p, q, l, r = list(map(int, input().split()))

def rl():
	a, b = list(map(int, input().split()))
	return a, b

x = [rl() for _ in range(p)]
xline = [False] * (RMAX+1)
for a, b in x:
	for i in range(a, b+1): xline[i] = True
y = [rl() for _ in range(q)]

def test(t):
	for a, b in y:
		for i in range(t+a, t+b+1):
			if i > RMAX: break
			if xline[i] == True: return 1
	return 0

ans = sum(test(t) for t in range(l, r+1))
print(ans)


p, q, l, r = list(map(int, input().split()))
bestMoments = 0

def enter(stringNum):
    res = []
    for st in range(stringNum):
        a, b = list(map(int, input().split()))
        for i in range(a, b+1):
            res.append(i)        
    return res
        
littleY = []
littleZ = []

littleY = enter(p)
littleZ = enter(q)

lenYandZ = len(littleY) + len(littleZ)

for i in range(l, r+1):
    currentZ = list([x+i for x in littleZ])
    if len(set(currentZ+littleY)) < lenYandZ:
        bestMoments += 1

print(bestMoments)


p, q, l, r = (int(x) for x in input().split())
tx, val = [], [False] * (r - l + 1)
for i in range(p):
    tx.append([int(x) for x in input().split()])
for i in range(q):
    c, d = (int(x) for x in input().split())
    for x in tx:
        for j in range(max(l, x[0] - d), min(r, x[1] - c) + 1):
            val[j - l] = True
print(sum(val))

x1=[]
x2=[]
p, q, l, r = map(int, input().split(' '))
for i in range(p):
    a, b = map(int, input().split(' '))
    x1.append([a, b])

for i in range(q):
    a, b = map(int, input().split(' '))
    x2.append([a, b])

ok2 = []

for a in x1:
    for b in x2:
        lo = a[0]-b[1]
        hi = a[1]-b[0]
        if hi >= r:
            hi = r
        if lo <= l:
            lo = l
        ok2.append([lo, hi])

ok = [i for i in ok2 if i[1]>=i[0]]
ok.sort()
total = 0
if len(ok)==0:
    print(0)
else: 
    intv = ok[0]
    for i in range(1, len(ok)):
        curr = ok[i]
        if curr[0] > intv[1]:
            if intv[1] == intv[0]:
                total += 1
            else:
                total += intv[1]-intv[0]+1
            intv = curr
        else:
            minim = [min(curr[0], intv[0]), max(curr[1], intv[1])]
            intv = minim

    if intv[1] == intv[0]:
        total += 1
    else:
        total += intv[1]-intv[0]+1
    print(total)

p, q, l, r = [int(x) for x in input().split()]
a = ''
b = ''
for i in range(p):
	x, y = [int(x) for x in input().split()]
	a += '0' * (x - len(a))
	a += '1' * (y - x + 1)
for i in range(q):
	x, y = [int(x) for x in input().split()]
	b += '0' * (x - len(b))
	b += '1' * (y - x + 1)
ans = 0
for i in range(l, r + 1):
	ans += 1 if any([x[0] == '1' and x[1] == '1' for x in zip(a, '0' * i + b)]) else 0
print(ans)


def main():
    p, q, l, r = map(int, input().split())
    ab, cd = [False] * 1001, [False] * 1001
    for _ in range(p):
        a, b = map(int, input().split())
        for i in range(a, b + 1):
            ab[i] = True
    for _ in range(q):
        a, b = map(int, input().split())
        for i in range(a, b + 1):
            cd[i] = True
    res = 0
    for i in range(l, r + 1):
        for t, f in enumerate(ab):
            if f and cd[t - i] and t >= i:
                res += 1
                break
    print(res)


def __starting_point():
    main()
__starting_point()