
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////////////////

ll n,m;
ll cal(vector<ll>v){
    sort(v.begin(),v.end());
    vector<l_l>a;
    ll vs=v.size();
    ll pos=0;
    while(pos<=vs-1){
        ll val=v[pos];
        ll cou=1;
        while(pos<=vs-2&&v[pos]==v[pos+1]){
            cou++;
            pos++;
        }
        a.pb(l_l(val,cou));
        pos++;
    }
    vector<ll>x,y;
    ll xs=0,ys=0;
    for(auto z:a){
        if(z.first%m<=m/2){
            x.pb(z.second);
            xs+=z.second;
        }else{
            y.pb(z.second);
            ys+=z.second;
        }
    }
    if(xs>ys){
        swap(xs,ys);
        swap(x,y);
    }
    ll dc=0;
    for(auto z:y){
        dc+=z/2;
    }
    dc=min(dc,(ys-xs)/2);
    ll res=0;
    res=xs+dc;
    
    return res;
}


int main(){fastio;
    cin>>n>>m;
    ll t=m/2+1;
    vector<ll>v[t];
    rep(i,0,n-1){
        ll c;cin>>c;
        ll d=c%m;
        if(d>=t)d=m-d;
        v[d].pb(c);
    }
    ll ans=0;
    rep(i,0,t-1){
        if(i==0||i*2==m){
            ans+=v[i].size()/2;
            continue;
        }
        //for(auto zzz:v[i])cout<<zzz<<" ";cout<<endl;
        ans+=cal(v[i]);
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
    return 0;
}




### Prompt

Please provide a CPP coded solution 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////////////////

ll n,m;
ll cal(vector<ll>v){
    sort(v.begin(),v.end());
    vector<l_l>a;
    ll vs=v.size();
    ll pos=0;
    while(pos<=vs-1){
        ll val=v[pos];
        ll cou=1;
        while(pos<=vs-2&&v[pos]==v[pos+1]){
            cou++;
            pos++;
        }
        a.pb(l_l(val,cou));
        pos++;
    }
    vector<ll>x,y;
    ll xs=0,ys=0;
    for(auto z:a){
        if(z.first%m<=m/2){
            x.pb(z.second);
            xs+=z.second;
        }else{
            y.pb(z.second);
            ys+=z.second;
        }
    }
    if(xs>ys){
        swap(xs,ys);
        swap(x,y);
    }
    ll dc=0;
    for(auto z:y){
        dc+=z/2;
    }
    dc=min(dc,(ys-xs)/2);
    ll res=0;
    res=xs+dc;
    
    return res;
}


int main(){fastio;
    cin>>n>>m;
    ll t=m/2+1;
    vector<ll>v[t];
    rep(i,0,n-1){
        ll c;cin>>c;
        ll d=c%m;
        if(d>=t)d=m-d;
        v[d].pb(c);
    }
    ll ans=0;
    rep(i,0,t-1){
        if(i==0||i*2==m){
            ans+=v[i].size()/2;
            continue;
        }
        //for(auto zzz:v[i])cout<<zzz<<" ";cout<<endl;
        ans+=cal(v[i]);
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
    return 0;
}




```