#include <iostream>
#include <vector>

#include <map>
using namespace std;
int getEqualNum(vector<int> &v1,int &noequal,int &equal)
{
	noequal=0;
	equal=0;
	int num=v1.size();
	if (num==0){
		return 0;
	}
	map<int,int> mapV;
	map<int,int>::iterator mit;
	for (int i=0;i<num;i++){
		mit=mapV.find(v1[i]);
		if (mit==mapV.end()){
			mapV.insert(map<int,int>::value_type(v1[i],1));
		}else{
			(*mit).second++;
		}
	}

	for (mit=mapV.begin();mit!=mapV.end();mit++){
		if ((*mit).second==1){
			noequal++;
		}else{
			noequal+=(*mit).second%2;
			equal+=(*mit).second/2;
		}
	}
	mapV.clear();
	return 0;
}
int getPair(vector<int> &v1,vector<int> &v2)
{
	int num1=v1.size();
	int num2=v2.size();
	if (num1==0 || num2==0){
		return 0;
	}
	if (num1==num2){
		v1.clear();
		v2.clear();
		return num1;
	}
	vector<int> *pMax;
	int maxNum=max(num1,num2);
	int minNum=min(num1,num2);
	if (num1>num2){
		pMax = &v1;
	}else{
		pMax=&v2;
	}
	int num;
	int noequal;
	int equal;
	getEqualNum(*pMax,noequal,equal);
	if (noequal<minNum){
		equal-=(minNum-noequal+1)/2;
	}
	num= minNum+equal;
	v1.clear();
	v2.clear();
	return num;
}


int main(int argc, char* argv[])
{
	int N,M;
	cin>>N>>M;
	if (M==1){
		cout<<N/2<<endl;
		return 0;
	}
	int i;
	int v;
	vector<int> *Mod = new vector<int>[M+1];
	for (i=0;i<N;i++){
		cin>>v;
		Mod[v%M].push_back(v);
	}
	size_t aw=0;
	aw+=Mod[0].size()/2;
	Mod[0].clear();
	for (i=1;i<M;i++){
		if (Mod[i].size()>0){
			if (i==M-i){
				aw += Mod[i].size()/2;
				continue;
			}else{
				aw+=getPair(Mod[i],Mod[M-i]);
			}
			int noequal;
			int equal;
			getEqualNum(Mod[i],noequal,equal);
			aw+=equal;
		}
	}
	cout<<aw<<endl;
	delete[] Mod;
	return 0;
}
### Prompt

Generate 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 <vector>

#include <map>
using namespace std;
int getEqualNum(vector<int> &v1,int &noequal,int &equal)
{
	noequal=0;
	equal=0;
	int num=v1.size();
	if (num==0){
		return 0;
	}
	map<int,int> mapV;
	map<int,int>::iterator mit;
	for (int i=0;i<num;i++){
		mit=mapV.find(v1[i]);
		if (mit==mapV.end()){
			mapV.insert(map<int,int>::value_type(v1[i],1));
		}else{
			(*mit).second++;
		}
	}

	for (mit=mapV.begin();mit!=mapV.end();mit++){
		if ((*mit).second==1){
			noequal++;
		}else{
			noequal+=(*mit).second%2;
			equal+=(*mit).second/2;
		}
	}
	mapV.clear();
	return 0;
}
int getPair(vector<int> &v1,vector<int> &v2)
{
	int num1=v1.size();
	int num2=v2.size();
	if (num1==0 || num2==0){
		return 0;
	}
	if (num1==num2){
		v1.clear();
		v2.clear();
		return num1;
	}
	vector<int> *pMax;
	int maxNum=max(num1,num2);
	int minNum=min(num1,num2);
	if (num1>num2){
		pMax = &v1;
	}else{
		pMax=&v2;
	}
	int num;
	int noequal;
	int equal;
	getEqualNum(*pMax,noequal,equal);
	if (noequal<minNum){
		equal-=(minNum-noequal+1)/2;
	}
	num= minNum+equal;
	v1.clear();
	v2.clear();
	return num;
}


int main(int argc, char* argv[])
{
	int N,M;
	cin>>N>>M;
	if (M==1){
		cout<<N/2<<endl;
		return 0;
	}
	int i;
	int v;
	vector<int> *Mod = new vector<int>[M+1];
	for (i=0;i<N;i++){
		cin>>v;
		Mod[v%M].push_back(v);
	}
	size_t aw=0;
	aw+=Mod[0].size()/2;
	Mod[0].clear();
	for (i=1;i<M;i++){
		if (Mod[i].size()>0){
			if (i==M-i){
				aw += Mod[i].size()/2;
				continue;
			}else{
				aw+=getPair(Mod[i],Mod[M-i]);
			}
			int noequal;
			int equal;
			getEqualNum(Mod[i],noequal,equal);
			aw+=equal;
		}
	}
	cout<<aw<<endl;
	delete[] Mod;
	return 0;
}
```