#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <utility>
#include <map>

using namespace std;

template <class RandomIt, class T>
ptrdiff_t num_element(RandomIt first, RandomIt last, T value, T lb_, T ub_) {
    RandomIt ub=upper_bound(first, last, make_pair(value, ub_));
    RandomIt lb=lower_bound(first ,last, make_pair(value, lb_));
    return ub-lb;
}

bool testcase_ends() {
    size_t N;
    int M;
    if (scanf("%zu %d", &N, &M) == EOF)
        return 1;

    vector<pair<int, int>> X(N);
    map<int, int> maxrem;
    for (size_t i=0; i<N; ++i) {
        scanf("%d", &X[i].first);
        X[i].second = X[i].first/M;
        X[i].first %= M;
        maxrem[X[i].first] = max(maxrem[X[i].first], X[i].second);
    }

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

    size_t res=0;
    for (int i=0; i<=M/2; ++i) {
        ptrdiff_t upper=num_element(X.begin(), X.end(), M-i, 0, 200000);
        ptrdiff_t lower=num_element(X.begin(), X.end(), i, 0, 200000);

        if (i == M-i || i == 0) {
            res += lower/2;
            continue;
        }

        ptrdiff_t pairs=min(upper, lower), remain=abs(upper-lower);

        if (remain < 2) {
            res += pairs;
            continue;
        }

        int k=(lower<upper? M-i:i);
        int ub=maxrem[k];
        ptrdiff_t cur=0;
        for (int j=0; j<=ub&&cur<=lower+upper; ++j)
            cur += num_element(X.begin(), X.end(), k, j, j)/2;

        res += min(cur+pairs, (upper+lower)/2);
    }

    printf("%zu\n", res);
    return 0;
}

int main() {
    bool solved=false;
    while (!testcase_ends())
        solved |= 1;

    return !solved;
}

### Prompt

Please provide a Cpp coded solution 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 <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <utility>
#include <map>

using namespace std;

template <class RandomIt, class T>
ptrdiff_t num_element(RandomIt first, RandomIt last, T value, T lb_, T ub_) {
    RandomIt ub=upper_bound(first, last, make_pair(value, ub_));
    RandomIt lb=lower_bound(first ,last, make_pair(value, lb_));
    return ub-lb;
}

bool testcase_ends() {
    size_t N;
    int M;
    if (scanf("%zu %d", &N, &M) == EOF)
        return 1;

    vector<pair<int, int>> X(N);
    map<int, int> maxrem;
    for (size_t i=0; i<N; ++i) {
        scanf("%d", &X[i].first);
        X[i].second = X[i].first/M;
        X[i].first %= M;
        maxrem[X[i].first] = max(maxrem[X[i].first], X[i].second);
    }

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

    size_t res=0;
    for (int i=0; i<=M/2; ++i) {
        ptrdiff_t upper=num_element(X.begin(), X.end(), M-i, 0, 200000);
        ptrdiff_t lower=num_element(X.begin(), X.end(), i, 0, 200000);

        if (i == M-i || i == 0) {
            res += lower/2;
            continue;
        }

        ptrdiff_t pairs=min(upper, lower), remain=abs(upper-lower);

        if (remain < 2) {
            res += pairs;
            continue;
        }

        int k=(lower<upper? M-i:i);
        int ub=maxrem[k];
        ptrdiff_t cur=0;
        for (int j=0; j<=ub&&cur<=lower+upper; ++j)
            cur += num_element(X.begin(), X.end(), k, j, j)/2;

        res += min(cur+pairs, (upper+lower)/2);
    }

    printf("%zu\n", res);
    return 0;
}

int main() {
    bool solved=false;
    while (!testcase_ends())
        solved |= 1;

    return !solved;
}

```