#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const int mod=1e9+7;
const vi emp;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int n,m;

int main(){
	cin>>n>>m;
	vi a(m),b(m);
	map<int,int> M;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int y=x%m;
		a[y]++;
		M[x]++;
		if(M[x]!=0&&M[x]%2==0) b[y]++;
	}
	int ans=a[0]/2;
	for(int i=1;i<(m+1)/2;i++){
		int j=m-i;
		ans+=min(a[i],a[j]);
		if(a[i]>a[j]){
			a[i]-=a[j];
			ans+=min(a[i]/2,b[i]);
		}
		else{
			a[j]-=a[i];
			ans+=min(a[j]/2,b[j]);
		}
	}
	if(m%2==0) ans+=a[m/2]/2;
	cout<<ans<<endl;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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 <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const int mod=1e9+7;
const vi emp;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int n,m;

int main(){
	cin>>n>>m;
	vi a(m),b(m);
	map<int,int> M;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int y=x%m;
		a[y]++;
		M[x]++;
		if(M[x]!=0&&M[x]%2==0) b[y]++;
	}
	int ans=a[0]/2;
	for(int i=1;i<(m+1)/2;i++){
		int j=m-i;
		ans+=min(a[i],a[j]);
		if(a[i]>a[j]){
			a[i]-=a[j];
			ans+=min(a[i]/2,b[i]);
		}
		else{
			a[j]-=a[i];
			ans+=min(a[j]/2,b[j]);
		}
	}
	if(m%2==0) ans+=a[m/2]/2;
	cout<<ans<<endl;
}
```