#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#define show_table(n, k, table) rep(i,n){ rep(j,k) cout << table[i][j] << " "; cout << endl;}

using namespace std;

template<class T> inline void chmax(T& a,T const& b){a=max(a,b);}
template<class T> inline void chmin(T& a,T const& b){a=min(a,b);}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,K; cin >> N >> K;
  vector<P> a(N);
  rep(i,N){
    cin >> a[i].second;
    a[i].first = a[i].second % K;
  }
  sort(ALL(a));
  vi same(K),cnt(K);
  rep(i,N) cnt[a[i].first]++;
  rep(i,N-1){
    if(a[i].second==a[i+1].second){
      same[a[i].first]++;
      i += 1;
    }
  }
  int ans = 0;
  // rep(i,K) cout << same[i] << " ";
  // cout << "" << endl;
  // rep(i,K) cout << cnt[i] << " ";
  // cout << "" << endl;
  ans += cnt[0]/2;
  int l = 1, r = K-1;
  while(l<=r){
    if(l==r) ans += cnt[l]/2;
    // else if(abs(same[l]-same[r])<=1) ans += min(cnt[l],cnt[r]);
    else{
      int c1,c2,s1,s2;
      c1 = cnt[l]; c2 = cnt[r]; s1 = same[l]; s2 = same[r];
      if(c1<c2) swap(c1,c2), swap(s1,s2);
      ans += c2 + min((c1-c2)/2,s1);
    }
    // cout << l <<" "<< ans << endl;
    l++; r--;
  }
  cout << ans << endl;
  return 0;
}
### Prompt

Develop a solution in CPP 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"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#define show_table(n, k, table) rep(i,n){ rep(j,k) cout << table[i][j] << " "; cout << endl;}

using namespace std;

template<class T> inline void chmax(T& a,T const& b){a=max(a,b);}
template<class T> inline void chmin(T& a,T const& b){a=min(a,b);}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,K; cin >> N >> K;
  vector<P> a(N);
  rep(i,N){
    cin >> a[i].second;
    a[i].first = a[i].second % K;
  }
  sort(ALL(a));
  vi same(K),cnt(K);
  rep(i,N) cnt[a[i].first]++;
  rep(i,N-1){
    if(a[i].second==a[i+1].second){
      same[a[i].first]++;
      i += 1;
    }
  }
  int ans = 0;
  // rep(i,K) cout << same[i] << " ";
  // cout << "" << endl;
  // rep(i,K) cout << cnt[i] << " ";
  // cout << "" << endl;
  ans += cnt[0]/2;
  int l = 1, r = K-1;
  while(l<=r){
    if(l==r) ans += cnt[l]/2;
    // else if(abs(same[l]-same[r])<=1) ans += min(cnt[l],cnt[r]);
    else{
      int c1,c2,s1,s2;
      c1 = cnt[l]; c2 = cnt[r]; s1 = same[l]; s2 = same[r];
      if(c1<c2) swap(c1,c2), swap(s1,s2);
      ans += c2 + min((c1-c2)/2,s1);
    }
    // cout << l <<" "<< ans << endl;
    l++; r--;
  }
  cout << ans << endl;
  return 0;
}
```