#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n, m;
int x[100000 + 5], md[100000 + 5], nokori[100000 + 5], pa[100000 + 5];
map<int, int> same;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, n) {
        cin >> x[i];
        md[x[i] % m]++;
        same[x[i]]++;
    }
    for (auto p : same) {
        pa[p.fi % m] += p.se / 2;
        if (p.se % 2 == 1) {
            nokori[p.fi % m]++;
        }
    }
    //rep(i, m) cout << nokori[i] << endl;
    int ans = md[0] / 2;
    if (m % 2 == 0) ans += md[m / 2] / 2;
    rep2(i, 1, m) {
        if (m % 2 == 0 && m / 2 == i) continue;
        ans += pa[i];
    }
    rep2(i, 1, m / 2 + 1) {
        if (m % 2 == 0 && i == m / 2) continue;
        if (nokori[i] < nokori[m - i]) {
            swap(nokori[i], nokori[m -i]);
            swap(pa[i], pa[m - i]);
        }
        ans += nokori[m - i];
        //cout << nokori[i] << " " << nokori[m - i] << endl;
        nokori[i] -= nokori[m - i];
        if (pa[m - i] * 2 >= nokori[i]) {
            if (nokori[i] % 2 == 0) {
                ans -= nokori[i] / 2;
                ans += nokori[i];
            }
            else {
                ans -= nokori[i] / 2;
                ans += nokori[i] - 1;
            }
        }
        else {
            ans -= pa[m - i];
            ans += pa[m - i] * 2;
        }

    }

    cout << ans << endl;
}

### 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;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n, m;
int x[100000 + 5], md[100000 + 5], nokori[100000 + 5], pa[100000 + 5];
map<int, int> same;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, n) {
        cin >> x[i];
        md[x[i] % m]++;
        same[x[i]]++;
    }
    for (auto p : same) {
        pa[p.fi % m] += p.se / 2;
        if (p.se % 2 == 1) {
            nokori[p.fi % m]++;
        }
    }
    //rep(i, m) cout << nokori[i] << endl;
    int ans = md[0] / 2;
    if (m % 2 == 0) ans += md[m / 2] / 2;
    rep2(i, 1, m) {
        if (m % 2 == 0 && m / 2 == i) continue;
        ans += pa[i];
    }
    rep2(i, 1, m / 2 + 1) {
        if (m % 2 == 0 && i == m / 2) continue;
        if (nokori[i] < nokori[m - i]) {
            swap(nokori[i], nokori[m -i]);
            swap(pa[i], pa[m - i]);
        }
        ans += nokori[m - i];
        //cout << nokori[i] << " " << nokori[m - i] << endl;
        nokori[i] -= nokori[m - i];
        if (pa[m - i] * 2 >= nokori[i]) {
            if (nokori[i] % 2 == 0) {
                ans -= nokori[i] / 2;
                ans += nokori[i];
            }
            else {
                ans -= nokori[i] / 2;
                ans += nokori[i] - 1;
            }
        }
        else {
            ans -= pa[m - i];
            ans += pa[m - i] * 2;
        }

    }

    cout << ans << endl;
}

```