#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n;
int m;
vector<int> x;
int mod[100010];
int same[100010];

int MOD(int num)
{
	return num % m;
}


int main()
{
	cin >> n >> m;

	x.assign(n,0);

	for(int i = 0;i < n;i++)
	{
		cin >> x[i];
	}
	
	//can sort
	sort(x.begin(),x.end());

	mod[MOD(x[0])]++;
	int cou = 1;

	for(int i = 1;i < n;i++)
	{
		if(x[i - 1] == x[i])
		{
			same[MOD(x[i])]+=cou;
			cou = 1 - cou;
		}
		else
		{
			cou = 1;
		}
		mod[MOD(x[i])]++;
	}

	//make pair

	int result = 0;

	for(int i = 0;i < m;i++)
	{
		int j = MOD(m - i);
		if(i > j) break;
		int sub;
		if(i == j)
		{
			sub = mod[i] / 2;
			result += sub;
			mod[i] -= sub * 2;
		}
		else
		{
			sub = min(mod[i],mod[j]);

			result += sub;
			mod[i] -= sub;
			mod[j] -= sub;
		}

		//cout << i << ":sub=" << sub << endl;
	}

	for(int i = 0;i < m;i++)
	{
		int remain = mod[i];
		int pair_c = same[i] * 2;
		//cout << "r=" << remain << " pair=" << pair_c << endl;
		int sub = min(remain , pair_c) / 2;
		//cout << "sub=" << sub << endl;
		result += sub;
	}

	cout << result << endl;
	return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n;
int m;
vector<int> x;
int mod[100010];
int same[100010];

int MOD(int num)
{
	return num % m;
}


int main()
{
	cin >> n >> m;

	x.assign(n,0);

	for(int i = 0;i < n;i++)
	{
		cin >> x[i];
	}
	
	//can sort
	sort(x.begin(),x.end());

	mod[MOD(x[0])]++;
	int cou = 1;

	for(int i = 1;i < n;i++)
	{
		if(x[i - 1] == x[i])
		{
			same[MOD(x[i])]+=cou;
			cou = 1 - cou;
		}
		else
		{
			cou = 1;
		}
		mod[MOD(x[i])]++;
	}

	//make pair

	int result = 0;

	for(int i = 0;i < m;i++)
	{
		int j = MOD(m - i);
		if(i > j) break;
		int sub;
		if(i == j)
		{
			sub = mod[i] / 2;
			result += sub;
			mod[i] -= sub * 2;
		}
		else
		{
			sub = min(mod[i],mod[j]);

			result += sub;
			mod[i] -= sub;
			mod[j] -= sub;
		}

		//cout << i << ":sub=" << sub << endl;
	}

	for(int i = 0;i < m;i++)
	{
		int remain = mod[i];
		int pair_c = same[i] * 2;
		//cout << "r=" << remain << " pair=" << pair_c << endl;
		int sub = min(remain , pair_c) / 2;
		//cout << "sub=" << sub << endl;
		result += sub;
	}

	cout << result << endl;
	return 0;
}

```