#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define LONG_INF 1000000000000000
int wow[200000] = {};
int moduloed[200000] = {};
int used[200000] = {};
int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < n;++i) {
		int tmp;
		cin >> tmp;
		wow[tmp%m]++;
		used[tmp]++;
	}
	for (int i = 0;i < 110000;++i) {
		moduloed[i%m] += used[i] / 2;
	}
	int ans = 0;
	for (int i = 1;i < m;++i) {
		if (i != (m - i)) {
			int hoge = min(wow[i], wow[m - i]);
			ans += hoge;
			wow[i] -= hoge;
			wow[m - i] -= hoge;
			if (wow[i] == 0) {
				ans += min(wow[m - i] / 2, moduloed[m - i]);
			}
			else {
				ans += min(wow[i] / 2, moduloed[i]);
			}
			wow[m - i] = 0;
			wow[i] = 0;
			moduloed[m - i] = 0;
			moduloed[i] = 0;
		}
	}
	if (m % 2 == 0) {
		ans += wow[m / 2] / 2;
	}
	ans += wow[0] / 2;
	cout << ans << endl;
	return 0;
}

### 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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define LONG_INF 1000000000000000
int wow[200000] = {};
int moduloed[200000] = {};
int used[200000] = {};
int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < n;++i) {
		int tmp;
		cin >> tmp;
		wow[tmp%m]++;
		used[tmp]++;
	}
	for (int i = 0;i < 110000;++i) {
		moduloed[i%m] += used[i] / 2;
	}
	int ans = 0;
	for (int i = 1;i < m;++i) {
		if (i != (m - i)) {
			int hoge = min(wow[i], wow[m - i]);
			ans += hoge;
			wow[i] -= hoge;
			wow[m - i] -= hoge;
			if (wow[i] == 0) {
				ans += min(wow[m - i] / 2, moduloed[m - i]);
			}
			else {
				ans += min(wow[i] / 2, moduloed[i]);
			}
			wow[m - i] = 0;
			wow[i] = 0;
			moduloed[m - i] = 0;
			moduloed[i] = 0;
		}
	}
	if (m % 2 == 0) {
		ans += wow[m / 2] / 2;
	}
	ans += wow[0] / 2;
	cout << ans << endl;
	return 0;
}

```