
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

int n, m;
int x[123456];
vector<int>slot[123456];
vector<int>conv[123456];
int amount[123456];

int main(void)
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i)scanf("%d", x + i);
	sort(x, x + n);
	for (int i = 0; i < n; ++i)
	{
		int modsl = x[i] % m;
		slot[modsl].push_back(x[i]);
	}
	for (int j = 0; j < m; ++j)
	{
		amount[j] = slot[j].size();
		if (amount[j] == 0)continue;
		for (auto itr = slot[j].begin(); itr != slot[j].end(); ++itr)
		{
			if (itr != slot[j].begin() && *(itr - 1) == *itr)
			{
				++conv[j].back();
			}
			else
			{
				conv[j].push_back(1);
			}
		}
		sort(conv[j].begin(), conv[j].end());
	}
	int ans = 0;
	ans += amount[0] / 2;
	if (m % 2 == 0)
	{
		ans += amount[m / 2] / 2;
	}
	int bar = (m / 2 + ((m % 2 == 0) ? 0 : 1));
	for (int ss = 1; ss < bar; ++ss)
	{
		int large = ss;
		int small = m - ss;
		if (amount[ss] < amount[m - ss])
		{
			int tmp = large;
			large = small;
			small = tmp;
		}
		//if (conv[large].empty())continue;
		while (!conv[large].empty() && amount[large] > amount[small])
		{
			if (conv[large].back() == 1)break;
			conv[large].back() -= 2;
			amount[large] -= 2;
			++ans;
			if (conv[large].back() <= 1)conv[large].pop_back();
		}
		ans += min(amount[large], amount[small]);
	}
	printf("%d\n", ans);
	return 0;
}

### Prompt

Create a solution in Cpp for 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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

int n, m;
int x[123456];
vector<int>slot[123456];
vector<int>conv[123456];
int amount[123456];

int main(void)
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i)scanf("%d", x + i);
	sort(x, x + n);
	for (int i = 0; i < n; ++i)
	{
		int modsl = x[i] % m;
		slot[modsl].push_back(x[i]);
	}
	for (int j = 0; j < m; ++j)
	{
		amount[j] = slot[j].size();
		if (amount[j] == 0)continue;
		for (auto itr = slot[j].begin(); itr != slot[j].end(); ++itr)
		{
			if (itr != slot[j].begin() && *(itr - 1) == *itr)
			{
				++conv[j].back();
			}
			else
			{
				conv[j].push_back(1);
			}
		}
		sort(conv[j].begin(), conv[j].end());
	}
	int ans = 0;
	ans += amount[0] / 2;
	if (m % 2 == 0)
	{
		ans += amount[m / 2] / 2;
	}
	int bar = (m / 2 + ((m % 2 == 0) ? 0 : 1));
	for (int ss = 1; ss < bar; ++ss)
	{
		int large = ss;
		int small = m - ss;
		if (amount[ss] < amount[m - ss])
		{
			int tmp = large;
			large = small;
			small = tmp;
		}
		//if (conv[large].empty())continue;
		while (!conv[large].empty() && amount[large] > amount[small])
		{
			if (conv[large].back() == 1)break;
			conv[large].back() -= 2;
			amount[large] -= 2;
			++ans;
			if (conv[large].back() <= 1)conv[large].pop_back();
		}
		ans += min(amount[large], amount[small]);
	}
	printf("%d\n", ans);
	return 0;
}

```