#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> a;
int n, M;
int Q(int k){
	int f = -1;
	for(int i = 0; i < k; i++){
		f = max(f, (a[i] + a[2*k-1-i]) % M);
	}
	for(int i = 0; i < (n - k); i++){
		int r = a[2*k + i] + a[2*n-1-i];
		if(r < M) return -1;
		f = max(f, r - M);
	}
	assert(f < M);
	return f;
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> M;
	a.resize(2*n);
	for(int i = 0; i < 2*n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int s = -1; // not
	int e = n; // fine
	while(s + 1 < e){
		int m = (s + e) / 2;
		if(Q(m) == -1){
			s = m;
		} else {
			e = m;
		}
	}
	s++;
	e = n;
	int ans = M;
	ans = min(ans, Q(e));
	ans = min(ans, Q(s));
	while(s + 3 < e){
		int m1 = (s + s + e) / 3;
		int m2 = (s + e + e) / 3;
		if(Q(m1) <= Q(m2)){
			e = m2;
		} else {
			s = m1;
		}
	}
	for(int m = s; m <= e; m++){
		ans = min(Q(m), ans);
	}
	cout << ans << endl;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<int> a;
int n, M;
int Q(int k){
	int f = -1;
	for(int i = 0; i < k; i++){
		f = max(f, (a[i] + a[2*k-1-i]) % M);
	}
	for(int i = 0; i < (n - k); i++){
		int r = a[2*k + i] + a[2*n-1-i];
		if(r < M) return -1;
		f = max(f, r - M);
	}
	assert(f < M);
	return f;
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> M;
	a.resize(2*n);
	for(int i = 0; i < 2*n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int s = -1; // not
	int e = n; // fine
	while(s + 1 < e){
		int m = (s + e) / 2;
		if(Q(m) == -1){
			s = m;
		} else {
			e = m;
		}
	}
	s++;
	e = n;
	int ans = M;
	ans = min(ans, Q(e));
	ans = min(ans, Q(s));
	while(s + 3 < e){
		int m1 = (s + s + e) / 3;
		int m2 = (s + e + e) / 3;
		if(Q(m1) <= Q(m2)){
			e = m2;
		} else {
			s = m1;
		}
	}
	for(int m = s; m <= e; m++){
		ans = min(Q(m), ans);
	}
	cout << ans << endl;
}

```