#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int N, M, X[100010];
vector <int> R[100010];
int p[100010];

void solve(){
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;i++)scanf("%d", X+i);
	for(int i=1;i<=N;i++)R[X[i] % M].pb(X[i]);
	for(int i=0;i<M;i++)sort(all(R[i]));
	rep(i, M){
		for(int j=0;j<sz(R[i]);){
			if(j < sz(R[i]) - 1 && R[i][j] == R[i][j+1])p[i]++, j += 2;
			else j++;
		}
	}
	int ans = 0;
	for(int i=1;M-i>i;i++){
		int c = min(sz(R[i]), sz(R[M-i]));
		int x = sz(R[i]) - c, y = sz(R[M-i]) - c;
		ans += min(x/2, p[i]) + min(y/2, p[M-i]);
		ans += c;
	}
	ans += sz(R[0]) / 2;
	if(M % 2 == 0){
		ans += sz(R[M/2]) / 2;
	}
	printf("%d", ans);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}
### Prompt

Please formulate a Cpp solution to 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int N, M, X[100010];
vector <int> R[100010];
int p[100010];

void solve(){
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;i++)scanf("%d", X+i);
	for(int i=1;i<=N;i++)R[X[i] % M].pb(X[i]);
	for(int i=0;i<M;i++)sort(all(R[i]));
	rep(i, M){
		for(int j=0;j<sz(R[i]);){
			if(j < sz(R[i]) - 1 && R[i][j] == R[i][j+1])p[i]++, j += 2;
			else j++;
		}
	}
	int ans = 0;
	for(int i=1;M-i>i;i++){
		int c = min(sz(R[i]), sz(R[M-i]));
		int x = sz(R[i]) - c, y = sz(R[M-i]) - c;
		ans += min(x/2, p[i]) + min(y/2, p[M-i]);
		ans += c;
	}
	ans += sz(R[0]) / 2;
	if(M % 2 == 0){
		ans += sz(R[M/2]) / 2;
	}
	printf("%d", ans);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}
```