#include "bits/stdc++.h"
using namespace std;
     
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
     
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll, ll>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

#define N 100001
#define K 100001
vi par(N); //親
vi ran(N); //木の深さ
vi num(N);

//n要素で初期化
void init(int n){
	int i;
	for (i = 0; i < n; i++) {
		par[i]=i;
		ran[i]=0;
		num[i] = 1;
	}
}

//木の根を求める
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}

//xとyの属する集合を併合
void unite(int x,int y){
	x=find(x);
	y=find(y);
	int numsum = num[x] + num[y];
	if(x==y){
		return;
	}
	if(ran[x]<ran[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(ran[x]==ran[y]){
			ran[x]++;
		}
	}
	num[x] = num[y] = numsum;
}

//xとyが同じ集合に属するか否か
bool same(int x,int y){
	return find(x)==find(y);
}


int main() {
  int n, m, i, j;
  cin >> n >> m;
  vi x(n);
  vii module(m, vi());
  for (i = 0; i < n; i++) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  for (i = 0; i < n; i++) {
    module[x[i] % m].push_back(x[i]);
  }
  int cnt = 0;
  cnt += module[0].size() / 2;
  int left = 1, right = m - 1;
  // for (i = 0; i < m; i++) {
  //   cout << i << " : ";
  //   for (j = 0; j < module[i].size(); j++) {
  //     cout << module[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << cnt << endl;
  while (left <= right) {
    if (left == right) {
      cnt += module[left].size() / 2;
      left++; right--;
      continue;
    }
    int m = min(module[left].size(), module[right].size());
    cnt += m;
    int small, big;
    if (module[left].size() >= module[right].size()) {
      small = right;
      big = left;
    }
    else {
      small = left;
      big = right;
    }
    int cnt2 = 0;
    int pre = -1;
    for (i = 0; i < module[big].size(); i++) {
      if (module[big][i] == pre) {
	cnt2++;
	pre = -1;
      }
      else {
	pre = module[big][i];
      }
    }
    cnt += min(cnt2, ((int)module[big].size() - m) / 2);
    left++; right--;
  }
  cout << cnt << endl;
 
  
			   
}

### Prompt

Your challenge is to write 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 "bits/stdc++.h"
using namespace std;
     
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
     
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll, ll>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

#define N 100001
#define K 100001
vi par(N); //親
vi ran(N); //木の深さ
vi num(N);

//n要素で初期化
void init(int n){
	int i;
	for (i = 0; i < n; i++) {
		par[i]=i;
		ran[i]=0;
		num[i] = 1;
	}
}

//木の根を求める
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}

//xとyの属する集合を併合
void unite(int x,int y){
	x=find(x);
	y=find(y);
	int numsum = num[x] + num[y];
	if(x==y){
		return;
	}
	if(ran[x]<ran[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(ran[x]==ran[y]){
			ran[x]++;
		}
	}
	num[x] = num[y] = numsum;
}

//xとyが同じ集合に属するか否か
bool same(int x,int y){
	return find(x)==find(y);
}


int main() {
  int n, m, i, j;
  cin >> n >> m;
  vi x(n);
  vii module(m, vi());
  for (i = 0; i < n; i++) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  for (i = 0; i < n; i++) {
    module[x[i] % m].push_back(x[i]);
  }
  int cnt = 0;
  cnt += module[0].size() / 2;
  int left = 1, right = m - 1;
  // for (i = 0; i < m; i++) {
  //   cout << i << " : ";
  //   for (j = 0; j < module[i].size(); j++) {
  //     cout << module[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << cnt << endl;
  while (left <= right) {
    if (left == right) {
      cnt += module[left].size() / 2;
      left++; right--;
      continue;
    }
    int m = min(module[left].size(), module[right].size());
    cnt += m;
    int small, big;
    if (module[left].size() >= module[right].size()) {
      small = right;
      big = left;
    }
    else {
      small = left;
      big = right;
    }
    int cnt2 = 0;
    int pre = -1;
    for (i = 0; i < module[big].size(); i++) {
      if (module[big][i] == pre) {
	cnt2++;
	pre = -1;
      }
      else {
	pre = module[big][i];
      }
    }
    cnt += min(cnt2, ((int)module[big].size() - m) / 2);
    left++; right--;
  }
  cout << cnt << endl;
 
  
			   
}

```