#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

const int MAX = 100111;
int N, M;
int A[100111];
int C[100111];
VI odd[100111];
VI even[100111];


const int INF = 1e9;

int main() {
    scanf("%d%d", &N, &M);
    REP (i, N) scanf("%d", A+i);
    REP (i, N) C[A[i]]++;
    REP (i, MAX) {
	if (C[i]) {
	    if (C[i] % 2) odd[i % M].push_back(C[i]);
	    else even[i % M].push_back(C[i]);
	}
    }
    
    int ans = 0;

    stack<int> st;

    REP (i, M) if (odd[i].size()) {
	st.push(i);
    }
    while (!st.empty()) {
	int v = st.top();
	if (odd[v].size()) {
	    int p = odd[v].back(); odd[v].pop_back();
	    int w = (M - v) % M;

	    if (odd[w].size()) {
		int q = odd[w].back(); odd[w].pop_back();
		ans++;
		p--;
		if (p) even[v].push_back(p);
		q--;
		if (q) even[w].push_back(q);
//		eprintf("oo %d %d\n", v, w);
	    } else if (even[w].size()) {
		int q = even[w].back(); even[w].pop_back();
		ans++;
		p--;
		if (p) { even[v].push_back(p); }
		q--;
		if (q) { odd[w].push_back(q); st.push(w); }
//		eprintf("oe %d %d\n", v, w);
	    } else {
		ans += p / 2;
	    }
	} else {
	    st.pop();
	}
    }

    REP (i, M) {
	EACH (e, even[i]) {
	    ans += *e / 2;
	}
    }


    printf("%d\n", 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<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

const int MAX = 100111;
int N, M;
int A[100111];
int C[100111];
VI odd[100111];
VI even[100111];


const int INF = 1e9;

int main() {
    scanf("%d%d", &N, &M);
    REP (i, N) scanf("%d", A+i);
    REP (i, N) C[A[i]]++;
    REP (i, MAX) {
	if (C[i]) {
	    if (C[i] % 2) odd[i % M].push_back(C[i]);
	    else even[i % M].push_back(C[i]);
	}
    }
    
    int ans = 0;

    stack<int> st;

    REP (i, M) if (odd[i].size()) {
	st.push(i);
    }
    while (!st.empty()) {
	int v = st.top();
	if (odd[v].size()) {
	    int p = odd[v].back(); odd[v].pop_back();
	    int w = (M - v) % M;

	    if (odd[w].size()) {
		int q = odd[w].back(); odd[w].pop_back();
		ans++;
		p--;
		if (p) even[v].push_back(p);
		q--;
		if (q) even[w].push_back(q);
//		eprintf("oo %d %d\n", v, w);
	    } else if (even[w].size()) {
		int q = even[w].back(); even[w].pop_back();
		ans++;
		p--;
		if (p) { even[v].push_back(p); }
		q--;
		if (q) { odd[w].push_back(q); st.push(w); }
//		eprintf("oe %d %d\n", v, w);
	    } else {
		ans += p / 2;
	    }
	} else {
	    st.pop();
	}
    }

    REP (i, M) {
	EACH (e, even[i]) {
	    ans += *e / 2;
	}
    }


    printf("%d\n", ans);

    return 0;
}


```