Little penguin Polo adores integer segments, that is, pairs of integers [l; r] (l ≤ r). 

He has a set that consists of n integer segments: [l_1; r_1], [l_2; r_2], ..., [l_{n}; r_{n}]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [l; r] to either segment [l - 1; r], or to segment [l; r + 1].

The value of a set of segments that consists of n segments [l_1; r_1], [l_2; r_2], ..., [l_{n}; r_{n}] is the number of integers x, such that there is integer j, for which the following inequality holds, l_{j} ≤ x ≤ r_{j}.

Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by k.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 10^5). Each of the following n lines contain a segment as a pair of integers l_{i} and r_{i} ( - 10^5 ≤ l_{i} ≤ r_{i} ≤ 10^5), separated by a space.

It is guaranteed that no two segments intersect. In other words, for any two integers i, j (1 ≤ i < j ≤ n) the following inequality holds, min(r_{i}, r_{j}) < max(l_{i}, l_{j}).


-----Output-----

In a single line print a single integer — the answer to the problem.


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

Output
2

Input
3 7
1 2
3 3
4 7

Output
0

Difficulty: interview

Starter code:

Solutions:
N,k=input().split()
N=int(N)
k=int(k)
x=0
for i in range(N):
    A,B=input().split()
    A=int(A)
    B=int(B)
    x+=(max(A,B)-min(A,B)+1)

answer=(x%k)
if(answer!=0):
    answer=k-answer

print(answer)


n, m = list(map(int, input().split()))
tot = sum([x[1] - x[0] + 1 for x in [[int(x) for x in input().split()] for i in range(n)]])
print((m - tot % m) % m)


n, k = map(int, input().split())
s = 0
for i in range(n):
    l, r = map(int, input().split())
    s += l - r
print((s - n) % k)

n, k = map(int, input().split())
print((sum(int(l) - int(r) for l, r in [input().split() for i in range(n)]) - n) % k)


import sys
import math
  
n, k = [int(x) for x in (sys.stdin.readline()).split()]

vsum = 0
for i in range(n):
    l, r = [int(x) for x in (sys.stdin.readline()).split()]
    vsum += (r - l + 1)
    
if(vsum % k == 0):
    print(0)
else:
    print(k - (vsum % k))


n, k = map(int, input().split())
val = 0
for i in range(n):
    l, r = map(int, input().split())
    val += r - l + 1
print((k - val % k) % k)

n, k = [int(x) for x in input().split()]
s = 0
for i in range(n):
	l, r = [int(x) for x in input().split()]
	s += r - l + 1
print((k - s % k) % k)


a=input().split()
n=int(a[0])
k=int(a[1])
p=0
for i in range(n):
    b=input().split()
    p=int(b[1])-int(b[0])+1+p


if p%k==0:
    print(0)
else:
    s=(k-(p%k))%k

    print(s)

def main():
    n, k = list(map(int, input().split()))
    res = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        res -= b - a + 1
    print(res % k)


def __starting_point():
    main()


__starting_point()

n, k = list(map(int, input().split()))

sum = 0
for i in range(0,n):
   l,r = list(map(int, input().split()))
   sum += r - l + 1
if (sum % k == 0):
   res = sum
else:
   res = (sum // k + 1) * k
print(res - sum)



l=list(map(int,input().split()))
n,k=l[0],l[1]
i=0
sum=0
while(i<n):
  l=list(map(int,input().split()))
  l=list(range(l[0],l[1]+1))
  sum+=len(l)
  i+=1
if(sum%k==0):
  print(0)
else:
  print(((sum//k)+1)*k - sum)
  


a=input().split(' ')
lista=[]
contador=0
contador2=0
for i in range(0,int(a[0])):
    b=input().split(' ')
    lista.append(b)
for j in range(0,len(lista)):
    contador+=int(lista[j][0])
    contador2+=int(lista[j][1])

formula=((contador-int(a[0]))-contador2)%int(a[-1])
print(formula)



q = lambda:map(int, input().split())
n, k = q()
a = []
for _ in range(n):
    a += [q()]
print((k - sum(r - l + 1 for l,r in a) % k) % k)

q=lambda:map(int,input().split())
n,k=q()
a=[]
while(n):
    a+=[q()]
    n-=1
print((k-sum(r-l+1 for l,r in a)%k)%k)

n,k = map(int,input().split())
arr = []
cnt = 0
for i in range(n):
    a,b =map(int,input().split())
    arr.append(a)
    arr.append(b)
    cnt+=(b-a+1)
m = cnt
if (cnt%k==0):print(0) ; quit()
print(k-(m%k))

n,k=map(int,input().split())
coverd=0
for i in range (0,n):
    start,end=map(int,input().split())
    coverd=coverd+(end-start+1)
    
coverd=coverd%k
if (coverd!=0):
    coverd=k-coverd
    
print(coverd)

n, k = list(map(int, input().split()))

p = 0
for _ in range(n):
    l, r = list(map(int, input().split()))
    p += r - l + 1

print(0) if k%p == 1 else print( (k - (p%k))%k )

# A. Police Recruits
n, k = list(map(int, input().split()))
res = 0
for i in range(n):
    start, end = list(map(int, input().split()))
    res += end - start + 1
print(0 if not res%k else k - res%k)


n,k=map(int,input().split())
L={""}
for i in range(n):
   m,f=input().split()
   for i in range (int(m),int(f)+1):
      L |= {i}
L.remove("")
x=len(L)
i=0
while x%k!=0:
   x+=1
   i+=1
print(i)

n,k=map(int,input().split())
L={""}
for i in range(n):
   m,f=input().split()
   for i in range (int(m),int(f)+1):
      L |= {i}
L.remove("")
x=len(L)
if x%k==0:
   print("0")
else:   
   print(k-x%k)

n,k=map(int,input().split())
L={""}
for i in range(n):
   m,f=input().split()
   for i in range (int(m),int(f)+1):
      L |= {i}
L.remove("")
x=len(L)
print((k-x%k)%k)

n,k=map(int,input().split())
L={""}
for i in range(n):
   m,f=map(int,input().split())
   for i in range (m,f+1):
      L |= {i}
L.remove("")
x=len(L)
print((k-x%k)%k)

n,k=input().split()
n,k=int(n),int(k)
L={""}
for i in range(n):
   m,f=input().split()
   for i in range (int(m),int(f)+1):
      L |= {i}
L.remove("")
x=len(L)
print((k-x%k)%k)