#include <bits/stdc++.h>

#define mp       make_pair
#define mt	  make_tuple
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF=1<<29;
const double EPS=1e-9;
const ll MOD = 1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

const int MAX_NM = 100100;
int N,M;
vector<int> X;
int mod_count[MAX_NM];
int ans;
bool is_pair[MAX_NM];
int pair_count[MAX_NM];
int main(){
  cin >> N >> M;
  X.resize(N);
  set<int> number;
  for (int i = 0; i < N; i++){
    cin >> X[i];
    mod_count[X[i] % M]++;
    if (is_pair[X[i]]){
      pair_count[X[i] % M]++;
      is_pair[X[i]] = false;
    }else{
      is_pair[X[i]] = true;
    }
  }
  sort(X.begin(), X.end());
  ans = 0;
  int res= mod_count[0] / 2;
  mod_count[0] -= 2 * res;
  ans += res;
  //mod_count[0] = 0;
  if (M % 2 == 0){
    int res = mod_count[M / 2] / 2;
    ans += res;
    mod_count[M / 2] -= 2 * res;
  }
  for (int i = 1; i < (M + 1) / 2; i++){
    int a = mod_count[i];
    int b = mod_count[M - i];
    int c = min(a, b);
    ans += c;
    mod_count[i] -= c;
    mod_count[M - i] -= c;
    if (mod_count[i] > 0){
      ans += min(mod_count[i] / 2, pair_count[i]);
    }else if (mod_count[M - i] > 0){
      ans += min(mod_count[M - i] / 2, pair_count[M - i]);
    }
  }
  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 mp       make_pair
#define mt	  make_tuple
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF=1<<29;
const double EPS=1e-9;
const ll MOD = 1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

const int MAX_NM = 100100;
int N,M;
vector<int> X;
int mod_count[MAX_NM];
int ans;
bool is_pair[MAX_NM];
int pair_count[MAX_NM];
int main(){
  cin >> N >> M;
  X.resize(N);
  set<int> number;
  for (int i = 0; i < N; i++){
    cin >> X[i];
    mod_count[X[i] % M]++;
    if (is_pair[X[i]]){
      pair_count[X[i] % M]++;
      is_pair[X[i]] = false;
    }else{
      is_pair[X[i]] = true;
    }
  }
  sort(X.begin(), X.end());
  ans = 0;
  int res= mod_count[0] / 2;
  mod_count[0] -= 2 * res;
  ans += res;
  //mod_count[0] = 0;
  if (M % 2 == 0){
    int res = mod_count[M / 2] / 2;
    ans += res;
    mod_count[M / 2] -= 2 * res;
  }
  for (int i = 1; i < (M + 1) / 2; i++){
    int a = mod_count[i];
    int b = mod_count[M - i];
    int c = min(a, b);
    ans += c;
    mod_count[i] -= c;
    mod_count[M - i] -= c;
    if (mod_count[i] > 0){
      ans += min(mod_count[i] / 2, pair_count[i]);
    }else if (mod_count[M - i] > 0){
      ans += min(mod_count[M - i] / 2, pair_count[M - i]);
    }
  }
  cout << ans << endl;
  
  return 0;
}

```