#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int M;
	while(~scanf("%d%d", &N, &M)) {
		map<int, int> cnt;
		rep(i, N) {
			int X;
			scanf("%d", &X);
			++ cnt[X];
		}
		vector<vector<vi>> v(2, vector<vi>(M));
		for(auto p : cnt)
			v[p.second % 2][p.first % M].push_back(p.second);
		int ans = 0;
		rep(x, M) {
			int y = (M - x) % M;
			if(x >= y) continue;
			while(1) {
				bool update = false;
				rep(d, 4) {
					int a = d < 2, b = d % 2 == 0;
					auto &p = v[a][x], &q = v[b][y];
					if(!p.empty() && !q.empty()) {
						int t = p.back(), u = q.back();
						p.pop_back();
						q.pop_back();
						++ ans;
						if(t > 1)
							v[a ^ 1][x].push_back(t - 1);
						if(u > 1)
							v[b ^ 1][y].push_back(u - 1);
						update = true;
						break;
					}
				}
				if(!update) break;
			}
		}
		rep(a, 2) rep(x, M) {
			for(int &t : v[a][x]) {
				ans += t / 2;
				t %= 2;
			}
			v[a][x].erase(remove(v[a][x].begin(), v[a][x].end(), 0), v[a][x].end());
		}
		rep(x, M) {
			int y = (M - x) % M;
			if(x != y) continue;
			rep(a, 2) {
				ans += v[a][x].size() / 2;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

### Prompt

Please formulate 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 "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int M;
	while(~scanf("%d%d", &N, &M)) {
		map<int, int> cnt;
		rep(i, N) {
			int X;
			scanf("%d", &X);
			++ cnt[X];
		}
		vector<vector<vi>> v(2, vector<vi>(M));
		for(auto p : cnt)
			v[p.second % 2][p.first % M].push_back(p.second);
		int ans = 0;
		rep(x, M) {
			int y = (M - x) % M;
			if(x >= y) continue;
			while(1) {
				bool update = false;
				rep(d, 4) {
					int a = d < 2, b = d % 2 == 0;
					auto &p = v[a][x], &q = v[b][y];
					if(!p.empty() && !q.empty()) {
						int t = p.back(), u = q.back();
						p.pop_back();
						q.pop_back();
						++ ans;
						if(t > 1)
							v[a ^ 1][x].push_back(t - 1);
						if(u > 1)
							v[b ^ 1][y].push_back(u - 1);
						update = true;
						break;
					}
				}
				if(!update) break;
			}
		}
		rep(a, 2) rep(x, M) {
			for(int &t : v[a][x]) {
				ans += t / 2;
				t %= 2;
			}
			v[a][x].erase(remove(v[a][x].begin(), v[a][x].end(), 0), v[a][x].end());
		}
		rep(x, M) {
			int y = (M - x) % M;
			if(x != y) continue;
			rep(a, 2) {
				ans += v[a][x].size() / 2;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

```