#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n,m;
vll x;
vll y;
unordered_map<lli,lli> inv;
vll z;
lli ans = 0;

int main(){
  cin >> n >> m;
  x = vll(n);
  for(lli i = 0;i < n;i++) cin >> x[i];
  y = vll(m);
  z = vll(m);
  for(lli i = 0;i < n;i++){
    y[x[i]%m]++;
    inv[x[i]]++;
  }
  for(auto x : inv){
    z[x.first%m] += x.second/2;
  }
  ans += y[0]/2;
  if(m%2 == 0) ans += y[m/2]/2;
  for(lli i = 1,j = m-1;i < j;i++,j--){
    if(y[i] < y[j]){
      ans += y[i];
      lli less = y[j]-y[i];
      ans += min(less/2, z[j]);
    }else{
      ans += y[j];
      lli less = y[i]-y[j];
      ans += min(less/2, z[i]);
    }
  }
  cout << ans << endl;
  return 0;

}

### 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 <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n,m;
vll x;
vll y;
unordered_map<lli,lli> inv;
vll z;
lli ans = 0;

int main(){
  cin >> n >> m;
  x = vll(n);
  for(lli i = 0;i < n;i++) cin >> x[i];
  y = vll(m);
  z = vll(m);
  for(lli i = 0;i < n;i++){
    y[x[i]%m]++;
    inv[x[i]]++;
  }
  for(auto x : inv){
    z[x.first%m] += x.second/2;
  }
  ans += y[0]/2;
  if(m%2 == 0) ans += y[m/2]/2;
  for(lli i = 1,j = m-1;i < j;i++,j--){
    if(y[i] < y[j]){
      ans += y[i];
      lli less = y[j]-y[i];
      ans += min(less/2, z[j]);
    }else{
      ans += y[j];
      lli less = y[i]-y[j];
      ans += min(less/2, z[i]);
    }
  }
  cout << ans << endl;
  return 0;

}

```