#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

template<class T> inline T cabs(const T &x) { return x > 0 ? x : (-x); }
template<class T> inline T gcd(const T &x, const T &y) { return (y == 0) ? x : gcd(y, x % y); }
template<class T> inline T sgn(const T &x) { return (x > 0) - (x < 0); }

#define dbg(x) cout << #x << " = " << (x) << endl
#define dbg2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define dbg3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl
#define dbg4(x,y,z,w) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #w << " = " << w << endl

#define out(x) cout << (x) << endl
#define out2(x,y) cout << (x) << " " << (y) << endl
#define out3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define out4(x,y,z,w) cout << (x) << " " << (y) << " " << (z) << " " << (w) << endl

const int maxN = 100000 + 10;

int N, M;
int X[maxN];

struct node {
    int val, cnt;
    inline bool operator<(const node &s) const {
        return cnt < s.cnt;
    }
};
node A[maxN]; int nA;

int odd[maxN], even[maxN];

int main()
{
    scanf("%d %d", &N, &M);
    memset(X, 0, sizeof(X));
    int xi;
    for(int i = 0; i < N; i ++) {
        scanf("%d", &xi);
        X[xi] ++;
    }
    nA = 0;
    for(int i = 1; i <= 100000; i ++) {
        if( X[i] ) {
            A[nA].val = i;
            A[nA].cnt = X[i];
            nA ++;
        }
    }
    memset(odd, 0, sizeof(odd));
    memset(even, 0, sizeof(even));
    for(int i = 0; i < nA; i ++) {
        int d = A[i].val % M;
        odd[ d ] += A[i].cnt % 2;
        even[d]  += (A[i].cnt / 2) * 2;
    }
    int ans = 0;
    for(int i = 0; i < M; i ++) {
        int a = i;
        int b = (M - a) % M;
        if( a == b ) {
            ans += odd[a] / 2;
            odd[a] %= 2;
            if( odd[a] ) {
                if( even[a] ) {
                    ans ++;
                    odd[a] --;
                    even[a] --;
                }
            }
        } else {
            int c = min(odd[a], odd[b]);
            ans += c;
            odd[a] -= c, odd[b] -= c;
            if( odd[a] ) {
                if( even[b] ) {
                    c = min(odd[a], even[b]);
                    ans += c;
                    odd[a] -= c, even[b] -= c;
                }
            }
            if( odd[b] ) {
                if( even[a] ) {
                    c = min(odd[b], even[a]);
                    ans += c;
                    odd[b] -= c, even[a] -= c;
                }
            }
        }
    }
    for(int i = 0; i < M; i ++)
        ans += even[i] / 2;
    out(ans);
    return 0;
}

### Prompt

Generate 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 <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

template<class T> inline T cabs(const T &x) { return x > 0 ? x : (-x); }
template<class T> inline T gcd(const T &x, const T &y) { return (y == 0) ? x : gcd(y, x % y); }
template<class T> inline T sgn(const T &x) { return (x > 0) - (x < 0); }

#define dbg(x) cout << #x << " = " << (x) << endl
#define dbg2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define dbg3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl
#define dbg4(x,y,z,w) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #w << " = " << w << endl

#define out(x) cout << (x) << endl
#define out2(x,y) cout << (x) << " " << (y) << endl
#define out3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define out4(x,y,z,w) cout << (x) << " " << (y) << " " << (z) << " " << (w) << endl

const int maxN = 100000 + 10;

int N, M;
int X[maxN];

struct node {
    int val, cnt;
    inline bool operator<(const node &s) const {
        return cnt < s.cnt;
    }
};
node A[maxN]; int nA;

int odd[maxN], even[maxN];

int main()
{
    scanf("%d %d", &N, &M);
    memset(X, 0, sizeof(X));
    int xi;
    for(int i = 0; i < N; i ++) {
        scanf("%d", &xi);
        X[xi] ++;
    }
    nA = 0;
    for(int i = 1; i <= 100000; i ++) {
        if( X[i] ) {
            A[nA].val = i;
            A[nA].cnt = X[i];
            nA ++;
        }
    }
    memset(odd, 0, sizeof(odd));
    memset(even, 0, sizeof(even));
    for(int i = 0; i < nA; i ++) {
        int d = A[i].val % M;
        odd[ d ] += A[i].cnt % 2;
        even[d]  += (A[i].cnt / 2) * 2;
    }
    int ans = 0;
    for(int i = 0; i < M; i ++) {
        int a = i;
        int b = (M - a) % M;
        if( a == b ) {
            ans += odd[a] / 2;
            odd[a] %= 2;
            if( odd[a] ) {
                if( even[a] ) {
                    ans ++;
                    odd[a] --;
                    even[a] --;
                }
            }
        } else {
            int c = min(odd[a], odd[b]);
            ans += c;
            odd[a] -= c, odd[b] -= c;
            if( odd[a] ) {
                if( even[b] ) {
                    c = min(odd[a], even[b]);
                    ans += c;
                    odd[a] -= c, even[b] -= c;
                }
            }
            if( odd[b] ) {
                if( even[a] ) {
                    c = min(odd[b], even[a]);
                    ans += c;
                    odd[b] -= c, even[a] -= c;
                }
            }
        }
    }
    for(int i = 0; i < M; i ++)
        ans += even[i] / 2;
    out(ans);
    return 0;
}

```