#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int m[100010],p[100010];

int main(void){
	int i;

	int N,M;
	cin >> N >> M;
	vector<int>v(N);
	for(i=0;i<N;i++) cin >> v[i];
	sort(v.begin(),v.end());
	for(i=0;i<N-1;i++){
		if(v[i]==v[i+1]){
			p[v[i]%M]++;
			i++;
		}
	}

	for(i=0;i<N;i++){
		m[v[i]%M]++;
	}

	if(M==1){
		cout << m[0]/2 << endl;
		return 0;
	}
	if(M==2){
		cout << m[0]/2+m[1]/2 << endl;
		return 0;
	}

	int ans=0;
	if(M%2==1){
		for(i=1;i<=(M-1)/2;i++){
			int x=min(m[i],m[M-i]);
			m[i]-=x;
			m[M-i]-=x;
			ans+=x;
		}

		ans+=m[0]/2;
		for(i=1;i<M;i++){
			if(2*p[i]<=m[i]) ans+=p[i];
			else ans+=m[i]/2;
		}

	}else{

		for(i=1;i<=M/2-1;i++){
			int x=min(m[i],m[M-i]);
			m[i]-=x;
			m[M-i]-=x;
			ans+=x;
		}

		ans+=m[0]/2;
		for(i=1;i<M;i++){
			if(i==M/2){
				ans+=m[i]/2;
				m[i]=0;
				continue;
			}

			if(2*p[i]<=m[i]) ans+=p[i];
			else ans+=m[i]/2;
		}

	}


	cout << ans << endl;


	return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

* The integers on the two cards are the same.
* The sum of the integers on the two cards is a multiple of M.



Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

* 2≦N≦10^5
* 1≦M≦10^5
* 1≦X_i≦10^5

Input

The input is given from Standard Input in the following format:


N M
X_1 X_2 ... X_N


Output

Print the maximum number of pairs that can be created.

Examples

Input

7 5
3 1 4 1 5 9 2


Output

3


Input

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99


Output

6

### Response

```cpp
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int m[100010],p[100010];

int main(void){
	int i;

	int N,M;
	cin >> N >> M;
	vector<int>v(N);
	for(i=0;i<N;i++) cin >> v[i];
	sort(v.begin(),v.end());
	for(i=0;i<N-1;i++){
		if(v[i]==v[i+1]){
			p[v[i]%M]++;
			i++;
		}
	}

	for(i=0;i<N;i++){
		m[v[i]%M]++;
	}

	if(M==1){
		cout << m[0]/2 << endl;
		return 0;
	}
	if(M==2){
		cout << m[0]/2+m[1]/2 << endl;
		return 0;
	}

	int ans=0;
	if(M%2==1){
		for(i=1;i<=(M-1)/2;i++){
			int x=min(m[i],m[M-i]);
			m[i]-=x;
			m[M-i]-=x;
			ans+=x;
		}

		ans+=m[0]/2;
		for(i=1;i<M;i++){
			if(2*p[i]<=m[i]) ans+=p[i];
			else ans+=m[i]/2;
		}

	}else{

		for(i=1;i<=M/2-1;i++){
			int x=min(m[i],m[M-i]);
			m[i]-=x;
			m[M-i]-=x;
			ans+=x;
		}

		ans+=m[0]/2;
		for(i=1;i<M;i++){
			if(i==M/2){
				ans+=m[i]/2;
				m[i]=0;
				continue;
			}

			if(2*p[i]<=m[i]) ans+=p[i];
			else ans+=m[i]/2;
		}

	}


	cout << ans << endl;


	return 0;
}

```