#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>

int main() {
    long long n, m;

    std::cin >> n >> m;

    std::vector<std::vector<long long> > remaining(m);
    for (size_t i = 0; i < n; i++) {
        long long num;
        std::cin >> num;
        remaining[num % m].push_back(num);
    }

    // あまりがゼロのものはそのものの半分ペアができる
    long long ans = remaining[0].size() / 2;

    for (int i = 1; i <= m / 2; i++) {
        std::vector<long long> a = remaining[i],
            b = remaining[m - i];

        if (a == b) {
            ans += a.size() / 2;
            continue;
        }

        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());

        if (a.size() > b.size()) std::swap(a, b);
        // この時点で b のほうがたくさん要素がある
        if (b.size() == 0) continue;
        for (auto it = b.begin() + 1;a.size() < b.size() && it < b.end(); it++) {
            if (*(it - 1) == *it) {
                it = b.erase(it);
                it = b.erase(it - 1);
                ans++;
            }
        }
        ans += std::min(a.size(), b.size());
    }

    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 <algorithm>
#include <vector>
#include <string>
#include <numeric>

int main() {
    long long n, m;

    std::cin >> n >> m;

    std::vector<std::vector<long long> > remaining(m);
    for (size_t i = 0; i < n; i++) {
        long long num;
        std::cin >> num;
        remaining[num % m].push_back(num);
    }

    // あまりがゼロのものはそのものの半分ペアができる
    long long ans = remaining[0].size() / 2;

    for (int i = 1; i <= m / 2; i++) {
        std::vector<long long> a = remaining[i],
            b = remaining[m - i];

        if (a == b) {
            ans += a.size() / 2;
            continue;
        }

        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());

        if (a.size() > b.size()) std::swap(a, b);
        // この時点で b のほうがたくさん要素がある
        if (b.size() == 0) continue;
        for (auto it = b.begin() + 1;a.size() < b.size() && it < b.end(); it++) {
            if (*(it - 1) == *it) {
                it = b.erase(it);
                it = b.erase(it - 1);
                ans++;
            }
        }
        ans += std::min(a.size(), b.size());
    }

    std::cout << ans << std::endl;

    return 0;
}
```