#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, a;
vector<int> V[N];

int get_same(int x){
	sort(V[x].begin(), V[x].end());
    int cnt = 1;
    int ret = 0;
    for(int i=1; i<V[x].size(); i++){
        if(V[x][i] == V[x][i-1]){
			cnt++;
        } else {
			ret = ret + cnt / 2;
			cnt = 1;
        }
    }
    ret = ret + cnt / 2;
    return ret;
}

int cal(int x, int y){
	int n = V[x].size();
	int m = V[y].size();
    int ret = min(n, m);
    int a = get_same(x);
    int b = get_same(y);
    int c = 0;
    while(a && b){
        if(n > m){
            n-=2;
            a--;
            c++;
        } else {
			m -= 2;
			b--;
			c++;
        }
        ret = max(ret, min(n, m) + c);
    }
    while(a){
		n-=2;
		a--;
		c++;
        ret = max(ret, min(n, m) + c);
    }
    while(b){
		m-=2;
		b--;
		c++;
        ret = max(ret, min(n, m) + c);
    }
    return ret;
}

int solve(){
    int ans = V[0].size() / 2;
    for(int i=1; i<m; i++){
		int j = m - i;
		if(j < i)	break;
        if(i == j){
			ans += V[i].size() / 2;
        } else {
            ans += cal(i, j);
        }
    }
    return ans;
}

int main(){
	while(~scanf("%d %d", &n, &m)){
		for(int i=0; i<m; i++){
			V[i].clear();
		}
		for(int i=0; i<n; i++){
			scanf("%d", &a);
			V[a%m].push_back(a);
		}
		printf("%d\n", solve());
	}
	return 0;
}

### Prompt

Your challenge is to write 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 <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, a;
vector<int> V[N];

int get_same(int x){
	sort(V[x].begin(), V[x].end());
    int cnt = 1;
    int ret = 0;
    for(int i=1; i<V[x].size(); i++){
        if(V[x][i] == V[x][i-1]){
			cnt++;
        } else {
			ret = ret + cnt / 2;
			cnt = 1;
        }
    }
    ret = ret + cnt / 2;
    return ret;
}

int cal(int x, int y){
	int n = V[x].size();
	int m = V[y].size();
    int ret = min(n, m);
    int a = get_same(x);
    int b = get_same(y);
    int c = 0;
    while(a && b){
        if(n > m){
            n-=2;
            a--;
            c++;
        } else {
			m -= 2;
			b--;
			c++;
        }
        ret = max(ret, min(n, m) + c);
    }
    while(a){
		n-=2;
		a--;
		c++;
        ret = max(ret, min(n, m) + c);
    }
    while(b){
		m-=2;
		b--;
		c++;
        ret = max(ret, min(n, m) + c);
    }
    return ret;
}

int solve(){
    int ans = V[0].size() / 2;
    for(int i=1; i<m; i++){
		int j = m - i;
		if(j < i)	break;
        if(i == j){
			ans += V[i].size() / 2;
        } else {
            ans += cal(i, j);
        }
    }
    return ans;
}

int main(){
	while(~scanf("%d %d", &n, &m)){
		for(int i=0; i<m; i++){
			V[i].clear();
		}
		for(int i=0; i<n; i++){
			scanf("%d", &a);
			V[a%m].push_back(a);
		}
		printf("%d\n", solve());
	}
	return 0;
}

```