#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; typedef long long ll; const int M = 998244353;

int main() {
  int n,m; cin>>n>>m; int x[n];
  for(int i=0;i<n;i++) {
    cin>>x[i];
  }
  int y[100001]; fill(y,y+100001,0);
  for(int i=0;i<n;i++) {
    y[x[i]]++;
  }
  int p[m]; fill(p,p+m,0);
  int q[m]; fill(q,q+m,0);
  for(int i=1;i<=100000;i++) {
    p[i%m] += y[i];
    if (y[i] >= 2) q[i%m] += y[i]/2;
  }
  ll an=0;
  for(int i=1,j=m-1;i<m && i<j;i++,j--) {
    if (p[i] >= p[j]) {
      an += p[j];
      int left = p[i] - p[j];
      an += min(left/2, q[i]);
    } else {
      an += p[i];
      int left = p[j] - p[i];
      an += min(left/2, q[j]);
    }
  }
  {
    an += p[0] / 2;
    if (m%2 == 0) {
      an += p[m/2] / 2;
    }
  }
  cout<<an<<endl;
}
### Prompt

Your task is to create 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 <iostream>
#include <vector>
#include <algorithm>
using namespace std; typedef long long ll; const int M = 998244353;

int main() {
  int n,m; cin>>n>>m; int x[n];
  for(int i=0;i<n;i++) {
    cin>>x[i];
  }
  int y[100001]; fill(y,y+100001,0);
  for(int i=0;i<n;i++) {
    y[x[i]]++;
  }
  int p[m]; fill(p,p+m,0);
  int q[m]; fill(q,q+m,0);
  for(int i=1;i<=100000;i++) {
    p[i%m] += y[i];
    if (y[i] >= 2) q[i%m] += y[i]/2;
  }
  ll an=0;
  for(int i=1,j=m-1;i<m && i<j;i++,j--) {
    if (p[i] >= p[j]) {
      an += p[j];
      int left = p[i] - p[j];
      an += min(left/2, q[i]);
    } else {
      an += p[i];
      int left = p[j] - p[i];
      an += min(left/2, q[j]);
    }
  }
  {
    an += p[0] / 2;
    if (m%2 == 0) {
      an += p[m/2] / 2;
    }
  }
  cout<<an<<endl;
}
```