#include<iostream>
#include<vector>
#include<set>
using namespace std;
 
int main(){
  int n, m, maxi = 0;
  std::cin >> n >> m;
  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    std::cin >> x[i];
    maxi = max(maxi, x[i]);
  }
  vector<int> mod(m, 0);
  for (int i = 0; i < n; i++) {
    mod[x[i]%m]++;
  }
  int ans = 0, tmp;
 
  for (int i = 1; 2*i <= m; i++) {
    if(2*i == m){
      tmp = mod[m/2]/2;
      ans += tmp;
      mod[m/2] -= tmp*2;
    }else{
      tmp = min(mod[i], mod[m - i]);
      ans += tmp;
      mod[i] -= tmp;
      mod[m - i] -= tmp;
    }
  }
  tmp = mod[0]/2;
  ans += tmp;
  mod[0] -= tmp*2;
  vector<int> s(maxi, 0);
  for (int i = 0; i < n; i++) {
    s[x[i]]++;
    if(s[x[i]] >= 2 and mod[x[i]%m] >= 2){
      s[x[i]] -= 2;
      mod[x[i]%m] -= 2;
      ans++;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}
### Prompt

Your challenge is to write 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<set>
using namespace std;
 
int main(){
  int n, m, maxi = 0;
  std::cin >> n >> m;
  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    std::cin >> x[i];
    maxi = max(maxi, x[i]);
  }
  vector<int> mod(m, 0);
  for (int i = 0; i < n; i++) {
    mod[x[i]%m]++;
  }
  int ans = 0, tmp;
 
  for (int i = 1; 2*i <= m; i++) {
    if(2*i == m){
      tmp = mod[m/2]/2;
      ans += tmp;
      mod[m/2] -= tmp*2;
    }else{
      tmp = min(mod[i], mod[m - i]);
      ans += tmp;
      mod[i] -= tmp;
      mod[m - i] -= tmp;
    }
  }
  tmp = mod[0]/2;
  ans += tmp;
  mod[0] -= tmp*2;
  vector<int> s(maxi, 0);
  for (int i = 0; i < n; i++) {
    s[x[i]]++;
    if(s[x[i]] >= 2 and mod[x[i]%m] >= 2){
      s[x[i]] -= 2;
      mod[x[i]%m] -= 2;
      ans++;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}
```