#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

int N,M;
int X[100010];
int s[100010];
int p[100010];

int main(){
	scanf("%d%d" , &N , &M);
	repp(i,0,N){
		scanf("%d" , X + i);
	}
	sort(X,X+N);
	repp(i,0,N){
		if(X[i] == X[i+1]){
			p[X[i]%M] += 2;
			++s[X[i]%M];
			++i;
		} else {
			++p[X[i]%M];
		}
	}
	int ans = p[0] / 2;
	if(M%2==0) ans += p[M/2] / 2;
	int w = (M+1) / 2;
	repp(i,1,w){
		int z = min(p[i],p[M-i]);
		ans += z;
		p[i] -= z;
		p[M-i] -= z;
		ans += min(s[i] , p[i]/2);
		ans += min(s[M-i] , p[M-i]/2);
	}
	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 <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

int N,M;
int X[100010];
int s[100010];
int p[100010];

int main(){
	scanf("%d%d" , &N , &M);
	repp(i,0,N){
		scanf("%d" , X + i);
	}
	sort(X,X+N);
	repp(i,0,N){
		if(X[i] == X[i+1]){
			p[X[i]%M] += 2;
			++s[X[i]%M];
			++i;
		} else {
			++p[X[i]%M];
		}
	}
	int ans = p[0] / 2;
	if(M%2==0) ans += p[M/2] / 2;
	int w = (M+1) / 2;
	repp(i,1,w){
		int z = min(p[i],p[M-i]);
		ans += z;
		p[i] -= z;
		p[M-i] -= z;
		ans += min(s[i] , p[i]/2);
		ans += min(s[M-i] , p[M-i]/2);
	}
	printf("%d\n" , ans);
	return 0;
}

```