You are given a positive integer $m$ and two integer sequence: $a=[a_1, a_2, \ldots, a_n]$ and $b=[b_1, b_2, \ldots, b_n]$. Both of these sequence have a length $n$.

Permutation is a sequence of $n$ different positive integers from $1$ to $n$. For example, these sequences are permutations: $[1]$, $[1,2]$, $[2,1]$, $[6,7,3,4,1,2,5]$. These are not: $[0]$, $[1,1]$, $[2,3]$.

You need to find the non-negative integer $x$, and increase all elements of $a_i$ by $x$, modulo $m$ (i.e. you want to change $a_i$ to $(a_i + x) \bmod m$), so it would be possible to rearrange elements of $a$ to make it equal $b$, among them you need to find the smallest possible $x$.

In other words, you need to find the smallest non-negative integer $x$, for which it is possible to find some permutation $p=[p_1, p_2, \ldots, p_n]$, such that for all $1 \leq i \leq n$, $(a_i + x) \bmod m = b_{p_i}$, where $y \bmod m$ — remainder of division of $y$ by $m$.

For example, if $m=3$, $a = [0, 0, 2, 1], b = [2, 0, 1, 1]$, you can choose $x=1$, and $a$ will be equal to $[1, 1, 0, 2]$ and you can rearrange it to make it equal $[2, 0, 1, 1]$, which is equal to $b$.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq n \leq 2000, 1 \leq m \leq 10^9$): number of elemens in arrays and $m$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < m$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i < m$).

It is guaranteed that there exists some non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$.


-----Output-----

Print one integer, the smallest non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$ for all $1 \leq i \leq n$.


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

Output
1

Input
3 2
0 0 0
1 1 1

Output
1

Input
5 10
0 0 0 1 2
2 1 0 0 0

Output
0

Difficulty: interview

Starter code:

Solutions:
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [u % m for u in a]
b = [u % m for u in b]
a.sort()
b.sort()
possible = set(sorted([(b[0] - u + m) % m for u in a])) # At most 2000 elements
# O(n^2)
for x in possible:
    array = [(u + x) % m for u in a]
    if sorted(array) == b:
        print (x)
        break

n,m=list(map(int,input().split()))
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
ss={}
for i in bb:
    try:
        ss[i]+=1
    except:
        ss[i]=1
mi=float("inf")
for i in range(n):
    
    x=(bb[i]-aa[0])%m
    cc=[(a+x)%m for a in aa]
    tt={}
    for i in cc:
        try:
            tt[i]+=1
        except:
            tt[i]=1
    if ss==tt:
        mi=min(mi,x)
print(mi)
        
    


n, m = list(map(int, input().split()))
arr1 = list(map(int, input().split()))
arr2 = sorted(list(map(int, input().split())))

best = float('inf')
for item in arr2:
    diff = item - arr1[0] if item >= arr1[0] else m - arr1[0] + item
    new = [(arr1[i] + diff) % m for i in range(n)]
    if sorted(new) == arr2:
        best = min(best, diff)
print(best)


from collections import deque
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
A = deque(A)
B.sort()
for _ in range(n+1):
    d = (A[0] - B[0]) % m
    for i in range(1, n):
        if (A[i] - B[i]) % m != d:
            d = -1
            break
    if d != -1:
        print(-d % m)
        return
    x = A.pop()
    A.appendleft(x)
print(-1)


# map(int, input().split())
# list(map(int, input().split()))

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

a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()

pos = [(b[i] - a[0])%m for i in range(n)]

for x in pos:
    new = [(a[i]+x)%m for i in range(n)]
    new.sort()
    if (new == b):
        print(x)
        break


import math

n, m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()

min_x = math.inf
for i in range(len(b)):
	x = (b[i] - a[0]) % m
	if x < min_x:
		new_a = [(y + x) % m for y in a]
		new_a.sort()
		if new_a == b:
			min_x = x
print(min_x)

import sys
import math
input = sys.stdin.readline

n,m=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))
alist.sort()
blist.sort()

minx=math.inf
for i in range(n):
	diff=(blist[0]-alist[i]+m)%m
	# print("diff",diff)
	arr=[]
	for j in range(n):
		arr.append((alist[j]+diff)%m)
	arr.sort()
	# print(arr)
	flag=True
	for j in range(n):
		if arr[j]!=blist[j]:
			flag=False
			break
	if flag:
		minx=min(minx,diff)

print(minx)

from collections import Counter
n, m = list(map(int, input().split()))
a = Counter(list(map(int, input().split())))
b = Counter(list(map(int, input().split())))
dct = {}
variants = Counter()
for i in a:
    if a[i] not in dct:
        dct[a[i]] = []
    dct[a[i]].append(i)
for i in b:
    count = b[i]
    for j in dct[count]:
        if i - j >= 0:
            variants[i - j] += 1
        else:
            variants[i - j + m] += 1
mx = -float('inf')
ans = 0
for i in variants:
    if variants[i] > mx or (variants[i] == mx and i < ans):
        ans = i
        mx = variants[i]
print(ans)


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
aa = inpl()
bb = inpl()
aa.sort()
bb.sort()

a0 = aa[0]
ans = 10**10
for b in set(bb):
    x = (b-a0)%M
    aa_dush = sorted([(a+x)%M for a in aa])

    for a,b in zip(bb,aa_dush):
        if a != b:
            break
    else:
        ans = min(ans,x)

print(ans)


n,m=map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
out = 1e9+1
for i in range(n):
  good = True
  dc = {}
  dif = (((b[i]-a[0])%m)+m)%m
  for j in range(n):
    if b[j] in dc:
      dc[b[j]] += 1
    else:
      dc[b[j]] = 1
  for j in range(n):
    if (a[j]+dif)%m in dc and dc[(a[j]+dif)%m] > 0:
      dc[(a[j]+dif)%m] -= 1
    else:
      good = False
      break
  if good:
    out = min(out,dif)
print(out)

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=m
for i in range(n):
    s=(m+b[i]-a[0])%m
    for j in range(n):
        if (a[j]+s)%m!=b[(i+j)%n]:
            break
    else:
        c=min(c,s)
print(c)




def __starting_point():
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    a.sort()
    b.sort()
    # print("b:", b)

    mindiff = float("inf")

    for i, num in enumerate(a):
        diff = (b[-1] - num) % m
        _a = [(i + diff) % m for i in a]
        _a.sort()
        # print("_a:", _a)
        if _a == b:
            mindiff = min(mindiff, diff)
    
    print(mindiff)

__starting_point()

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.sort()
b.sort()
ans=[]
for i in range(n):
	if b[-1]<a[i]:
		ans.append(b[-1]-a[i]+m)
		#ans.append(b[-1]-a[i]+m+m)
	else:
		ans.append(b[-1]-a[i])
		#ans.append(b[-1]-a[i]+m)
ans=list(set(ans))
ans.sort()
for i in ans:
	temp=[]
	for j in range(n):
		temp.append((a[j]+i)%m)
	if sorted(temp)==b:
		print (i)
		return
print(1/0)
	



n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort()

for j in range(n):
    c = b[j:] + b[:j]
    diff = []
    for i in range(n):
        diff.append((c[i] - a[i]) % m)
    if diff.count(diff[0]) == n:
        print(diff[0] % m)
        break


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
da={}
db={}
for i in a:
	da[i]=da.get(i,0)+1
for i in b:
	db[i]=db.get(i,0)+1
x=1000000001
ca={}
cb={}
for i in da:
	try:
		ca[da[i]].append(i)
	except:
		ca[da[i]]=[i]
for i in db:
	try:
		cb[db[i]].append(i)
	except:
		cb[db[i]]=[i]
ans={}
for i in ca:
	for j in ca[i]:
		for k in cb[i]:
			ans[(k-j)%m]=ans.get((k-j)%m,0)+1
l=len(da)
for i in ans:
	if ans[i]==l:
		x=min(x,i)
print(x)