#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;

long long N, M;
//    
map<long long, long long> num;
//
map<long long, long long> modnum;
//
map<long long, set<long long> > modset;

int main(){
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		long long tmp;
		cin >> tmp;
		num[tmp]++;
		modnum[tmp%M]++;
		modset[tmp%M].insert(tmp);
	}

	long long ans = 0;
	set<long long> done;
	for(auto mod: modnum){
		long long f = mod.first;
		long long s = (M - mod.first)%M;
		if(done.count(f) != 0){
			continue;
		}
		done.insert(f);
		done.insert(s);
		if(f == s){
			ans += modnum[f]/2;
		}else{
			if(modnum[f] > modnum[s]){
				swap(f, s);
			}
			for(auto inter: modset[s]){
				while(num[inter] > 1 && modnum[f] <= modnum[s] - 2){
					num[inter] -= 2;
					modnum[s] -= 2;
					ans++;
					//cout << "make pair with " << inter << endl;
				}
			}
			long long nn = min(modnum[f], modnum[s]);
			//cout << "make " << f << " and " << s << " num = " << nn<< endl;
			ans += nn;
			modnum[f] -= nn;
			modnum[s] -= nn;
		}
	}

	cout << ans << endl;

}

### 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 <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;

long long N, M;
//    
map<long long, long long> num;
//
map<long long, long long> modnum;
//
map<long long, set<long long> > modset;

int main(){
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		long long tmp;
		cin >> tmp;
		num[tmp]++;
		modnum[tmp%M]++;
		modset[tmp%M].insert(tmp);
	}

	long long ans = 0;
	set<long long> done;
	for(auto mod: modnum){
		long long f = mod.first;
		long long s = (M - mod.first)%M;
		if(done.count(f) != 0){
			continue;
		}
		done.insert(f);
		done.insert(s);
		if(f == s){
			ans += modnum[f]/2;
		}else{
			if(modnum[f] > modnum[s]){
				swap(f, s);
			}
			for(auto inter: modset[s]){
				while(num[inter] > 1 && modnum[f] <= modnum[s] - 2){
					num[inter] -= 2;
					modnum[s] -= 2;
					ans++;
					//cout << "make pair with " << inter << endl;
				}
			}
			long long nn = min(modnum[f], modnum[s]);
			//cout << "make " << f << " and " << s << " num = " << nn<< endl;
			ans += nn;
			modnum[f] -= nn;
			modnum[s] -= nn;
		}
	}

	cout << ans << endl;

}

```