#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200005

using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;

int main(){
	int n,m;
	//vi x(n);
	cin >> n >> m;
	int res[114514]={0};
	int cnt[114514]={0};
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int r=x%m;
		res[r]++;
		cnt[x]++;
	}
	int ans=0;
	if(m%2==0){
		ans=ans+res[m/2]/2;
		res[m/2]=0;
	}
	ans+=res[0]/2;
	res[0]=0;
	for(int i=1;i<=(m-1)/2;i++){
		int xx=min(res[i],res[m-i]);
		res[i]-=xx;
		res[m-i]-=xx;
		ans+=xx;
	}
	for(int i=0;i<100005;i++){
		int ii=i%m;
		int y=min(cnt[i],res[ii]);
		y=y/2;
		ans+=y;
		res[ii]=res[ii]-y*2;
	}	
	cout<<ans<<endl;
}

### Prompt

Create a solution in cpp for 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 <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200005

using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;

int main(){
	int n,m;
	//vi x(n);
	cin >> n >> m;
	int res[114514]={0};
	int cnt[114514]={0};
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int r=x%m;
		res[r]++;
		cnt[x]++;
	}
	int ans=0;
	if(m%2==0){
		ans=ans+res[m/2]/2;
		res[m/2]=0;
	}
	ans+=res[0]/2;
	res[0]=0;
	for(int i=1;i<=(m-1)/2;i++){
		int xx=min(res[i],res[m-i]);
		res[i]-=xx;
		res[m-i]-=xx;
		ans+=xx;
	}
	for(int i=0;i<100005;i++){
		int ii=i%m;
		int y=min(cnt[i],res[ii]);
		y=y/2;
		ans+=y;
		res[ii]=res[ii]-y*2;
	}	
	cout<<ans<<endl;
}

```