AtCoder Grand Contest 032 - Modulo Pairing

Let M be a positive integer.

You are given 2 N integers a_1, a_2, \ldots, a_{2 N}, where 0 \leq a_i < M for each i.

Consider dividing the 2 N integers into N pairs. Here, each integer must belong to exactly one pair.

We define the ugliness of a pair (x, y) as (x + y) \mod M. Let Z be the largest ugliness of the N pairs. Find the minimum possible value of Z.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 1 \leq M \leq 10^9
* 0 \leq a_i < M

Input

Input is given from Standard Input in the following format:


N M
a_1 a_2 \cdots a_{2N}


Output

Print the minimum possible value of Z, where Z is the largest ugliness of the N pairs.

Examples

Input

3 10
0 2 3 4 5 9


Output

5


Input

2 10
1 9 1 9


Output

0

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def modulo_pairing(N: int, M: int, A: list) -> int:
	A.sort()

	def check(n: int) -> bool:
		for i in range(2 * n, N + n):
			if A[i] + A[2 * N + 2 * n - i - 1] < M:
				return False
		return True
	(l, r) = (-1, N + 1)
	while r - l > 1:
		m = (l + r) // 2
		if check(m):
			r = m
		else:
			l = m
	blue = [A[i] + A[2 * r - i - 1] for i in range(r)]
	red = [A[i] + A[2 * N + 2 * r - i - 1] - M for i in range(2 * r, N + r)]
	return max(blue + red)
(N, M) = map(int, input().split())
A = [int(s) for s in input().split()]
ans = modulo_pairing(N, M, A)
print(ans)


def check(k):
	ret = 0
	b = 2 * k - 1
	for j in range(k):
		t = aaa[j] + aaa[b - j]
		if t >= m:
			return -1
		ret = max(ret, t)
	b = 2 * k
	c = 2 * n - 1
	for j in range(n - k):
		t = aaa[b + j] + aaa[c - j]
		if t < m:
			return -2
		ret = max(ret, t - m)
	return ret
(n, m) = map(int, input().split())
aaa = sorted(map(int, input().split()))
(l, r) = (0, n)
ans = -1
while l < r:
	mid = (l + r) // 2
	res = check(mid)
	if res == -1:
		r = mid
	elif res == -2:
		l = mid + 1
	else:
		ans = res
		r = mid
if ans == -1:
	ans = check(n)
print(ans)


(n, m) = map(int, input().split())
a = sorted([int(x) for x in input().split()])

def chk(x):
	for i in range(2 * x, 2 * n):
		if i != 2 * n - 1 - (i - 2 * x) and a[i] + a[2 * n - 1 - (i - 2 * x)] < m:
			return False
	return True
bottom = -1
top = n
while top - bottom > 1:
	mid = (top + bottom) // 2
	if chk(mid):
		top = mid
	else:
		bottom = mid
ans = -1
for i in range(2 * top, 2 * n):
	ans = max(ans, (a[i] + a[2 * n - 1 - (i - 2 * top)]) % m)
for i in range(2 * top):
	ans = max(ans, (a[i] + a[2 * top - 1 - i]) % m)
print(ans)