#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <cassert>
using namespace std;
using VI = vector<long>;

int n, m;
int modulo[101010];
int pairs[101010];
map<int, map<int, int>> mp;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        modulo[x % m]++;
        if (mp[x % m].count(x) != 0) {
            pairs[x % m]++;
            mp[x % m].erase(x);
        } else {
            mp[x % m][x] = 1;
        }
    }
    
    long ans = 0;
    for (int i = 1; i < m; i++) {
        if (i >= m - i) {
            if (i == m - i) {
                ans += modulo[i] / 2;
                modulo[i] -= modulo[i] / 2 * 2;
//                cout << "modulo " << i << " has " << modulo[i] / 2 << " pairs" << endl;
            }
            break;
        }
        long p = min(modulo[i], modulo[m - i]);
//        cout << "modulo " << i << " and modulo " << m - i << " have " << p << " pairs" << endl;
        ans += p;
        modulo[i] -= p;
        modulo[m - i] -= p;
    }
    
    for (int i = 1; i < m; i++) {
        if (modulo[i] != 0) {
            ans += min(pairs[i], modulo[i] / 2);
//            cout << "modulo " << i << " has " << modulo[i] / 2 << " pairs" << endl;
        }
    }
    
//    cout << "modulo 0 has " << modulo[0] / 2 << " pairs" << endl;
    ans += modulo[0] / 2;
    cout << ans << endl;
}

### Prompt

Generate 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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <cassert>
using namespace std;
using VI = vector<long>;

int n, m;
int modulo[101010];
int pairs[101010];
map<int, map<int, int>> mp;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        modulo[x % m]++;
        if (mp[x % m].count(x) != 0) {
            pairs[x % m]++;
            mp[x % m].erase(x);
        } else {
            mp[x % m][x] = 1;
        }
    }
    
    long ans = 0;
    for (int i = 1; i < m; i++) {
        if (i >= m - i) {
            if (i == m - i) {
                ans += modulo[i] / 2;
                modulo[i] -= modulo[i] / 2 * 2;
//                cout << "modulo " << i << " has " << modulo[i] / 2 << " pairs" << endl;
            }
            break;
        }
        long p = min(modulo[i], modulo[m - i]);
//        cout << "modulo " << i << " and modulo " << m - i << " have " << p << " pairs" << endl;
        ans += p;
        modulo[i] -= p;
        modulo[m - i] -= p;
    }
    
    for (int i = 1; i < m; i++) {
        if (modulo[i] != 0) {
            ans += min(pairs[i], modulo[i] / 2);
//            cout << "modulo " << i << " has " << modulo[i] / 2 << " pairs" << endl;
        }
    }
    
//    cout << "modulo 0 has " << modulo[0] / 2 << " pairs" << endl;
    ans += modulo[0] / 2;
    cout << ans << endl;
}

```