#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;
struct edge{int from, to; ll cost;};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    map<int, int> cards[m];
    vector<int> counts(m, 0);
    rep(n){
        int tmp;
        cin >> tmp;
        cards[tmp%m][tmp]++;
        counts[tmp%m]++;
    }

    int ans = counts[0] / 2;
    reppp(i, 1, (m-1)/2){
        if(counts[i] < counts[m-i]){
            swap(counts[i], counts[m-i]);
            swap(cards[i], cards[m-i]);
        }
        int diff = counts[i] - counts[m-i];
        if(diff >= 2){
            for(auto itr=cards[i].begin(); itr!=cards[i].end(); ++itr){
                if(itr->second >= 2){
                    int tmp = min(diff, itr->second)/2;
                    ans += tmp;
                    counts[i] -= tmp*2;
                    diff = counts[i] - counts[m-i];
                    if(diff == 0) break;
                }
            }
        }
        ans += min(counts[i], counts[m-i]);
        //cout << i << " " << ans << endl;

    }
    if(m % 2 == 0){
        ans += counts[m/2]/2;
    }
    cout << ans;
}

### Prompt

Develop a solution in CPP to the problem described below:

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<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;
struct edge{int from, to; ll cost;};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    map<int, int> cards[m];
    vector<int> counts(m, 0);
    rep(n){
        int tmp;
        cin >> tmp;
        cards[tmp%m][tmp]++;
        counts[tmp%m]++;
    }

    int ans = counts[0] / 2;
    reppp(i, 1, (m-1)/2){
        if(counts[i] < counts[m-i]){
            swap(counts[i], counts[m-i]);
            swap(cards[i], cards[m-i]);
        }
        int diff = counts[i] - counts[m-i];
        if(diff >= 2){
            for(auto itr=cards[i].begin(); itr!=cards[i].end(); ++itr){
                if(itr->second >= 2){
                    int tmp = min(diff, itr->second)/2;
                    ans += tmp;
                    counts[i] -= tmp*2;
                    diff = counts[i] - counts[m-i];
                    if(diff == 0) break;
                }
            }
        }
        ans += min(counts[i], counts[m-i]);
        //cout << i << " " << ans << endl;

    }
    if(m % 2 == 0){
        ans += counts[m/2]/2;
    }
    cout << ans;
}

```