#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> X(N);
  for (auto &i : X) cin >> i;

  sort(X.begin(), X.end());

  vector<vector<int>> a(M);
  for (auto &i : X) a[i % M].push_back(i);

  int ans = a[0].size() / 2;
  if (M % 2 == 0) {
    ans += a[M / 2].size() / 2;
  }

  for (int i = 1; i <= (M - 1) / 2; ++i) {
    int s = i, t = M - i;
    if (a[s].size() > a[t].size()) swap(s, t);

    ans += a[s].size();

    int cnt = 0;
    for (int j = 1; j < a[t].size(); ++j) {
      if (a[t][j] == a[t][j - 1]) {
        cnt++;
        j++;
      }
    }

    ans += min((int)(a[t].size() - a[s].size()) / 2, cnt);
  }

  cout << ans << endl;
}

### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> X(N);
  for (auto &i : X) cin >> i;

  sort(X.begin(), X.end());

  vector<vector<int>> a(M);
  for (auto &i : X) a[i % M].push_back(i);

  int ans = a[0].size() / 2;
  if (M % 2 == 0) {
    ans += a[M / 2].size() / 2;
  }

  for (int i = 1; i <= (M - 1) / 2; ++i) {
    int s = i, t = M - i;
    if (a[s].size() > a[t].size()) swap(s, t);

    ans += a[s].size();

    int cnt = 0;
    for (int j = 1; j < a[t].size(); ++j) {
      if (a[t][j] == a[t][j - 1]) {
        cnt++;
        j++;
      }
    }

    ans += min((int)(a[t].size() - a[s].size()) / 2, cnt);
  }

  cout << ans << endl;
}

```