#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int num[100010];
vector<int> v[100010];
int mnum[100010];

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> X(N);
  for(int i=0;i<N;i++) cin>>X[i];

  for(int i=0;i<N;i++){
      num[X[i]]++;
  }

  for(int i=1;i<=100000;i++){
      if(num[i]==0) continue;
      if(num[i]%2){
          mnum[i%M]++;
          num[i]--;
      }
      v[i%M].push_back(num[i]);
  }

  int ans=0;
  ans=mnum[0]/2;
  mnum[0]%=2;
  for(int i=1;i<M;i++){
      if(M-i<i) break;
      else if(M-i==i){
          ans+=mnum[i]/2;
          mnum[i]%=2;
          continue;
      }
      int mi=min(mnum[i],mnum[M-i]);
      ans+=mi;
      mnum[i]-=mi;
      mnum[M-i]-=mi;
  }

  for(int i=1;i<M;i++){
      if(mnum[i]==0) continue;
      for(int j=0;j<v[M-i].size();j++){
          if(mnum[i]<=1) break;

          int mi=min(mnum[i]/2,v[M-i][j]/2);
          ans+=mi*2;
          mnum[i]-=mi*2;
          v[M-i][j]-=mi*2;
      }
  }

  for(int i=0;i<M;i++){
      for(int j=0;j<v[i].size();j++){
          ans+=v[i][j]/2;
      }
  }
  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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int num[100010];
vector<int> v[100010];
int mnum[100010];

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> X(N);
  for(int i=0;i<N;i++) cin>>X[i];

  for(int i=0;i<N;i++){
      num[X[i]]++;
  }

  for(int i=1;i<=100000;i++){
      if(num[i]==0) continue;
      if(num[i]%2){
          mnum[i%M]++;
          num[i]--;
      }
      v[i%M].push_back(num[i]);
  }

  int ans=0;
  ans=mnum[0]/2;
  mnum[0]%=2;
  for(int i=1;i<M;i++){
      if(M-i<i) break;
      else if(M-i==i){
          ans+=mnum[i]/2;
          mnum[i]%=2;
          continue;
      }
      int mi=min(mnum[i],mnum[M-i]);
      ans+=mi;
      mnum[i]-=mi;
      mnum[M-i]-=mi;
  }

  for(int i=1;i<M;i++){
      if(mnum[i]==0) continue;
      for(int j=0;j<v[M-i].size();j++){
          if(mnum[i]<=1) break;

          int mi=min(mnum[i]/2,v[M-i][j]/2);
          ans+=mi*2;
          mnum[i]-=mi*2;
          v[M-i][j]-=mi*2;
      }
  }

  for(int i=0;i<M;i++){
      for(int j=0;j<v[i].size();j++){
          ans+=v[i][j]/2;
      }
  }
  cout<<ans<<endl;

  return 0;
}

```