#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> G[100000];

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int X;
        cin >> X;
        G[X%M].push_back(X);
    }
    for(int i = 0; i < M; i++){
        sort(G[i].begin(), G[i].end());
    }
    int cnt_all[100000] = {0};
    int cnt_odd[100000] = {0};
    for(int i = 0; i < M; i++){
        if(G[i].size() == 0) continue;
        int prev = G[i][0];
        int cnt_cur = 1;
        cnt_all[i] = G[i].size();
        for(int j = 1; j < G[i].size(); j++){
            //cout << j << endl;
            if(prev == G[i][j]){
                cnt_cur++;
            }else{
                if(cnt_cur%2 == 1)cnt_odd[i]++;
                prev = G[i][j];
                cnt_cur = 1;
            }
        }
    }
    int ans = G[0].size()/2;
    if(M%2 == 0) ans += G[M/2].size()/2;
    for(int i = 1; 2*i < M; i++){
        int k, l;
        if(G[i].size() < G[M-i].size()){
            k = i;
            l = M-i;
        }else{
            k = M-i;
            l = i;
        }
        if((G[l].size() - G[k].size()) <= cnt_all[l]-cnt_odd[l]){
            ans += G[k].size() + (G[l].size() - G[k].size())/2;
        }else{
            ans += G[k].size() + (cnt_all[l]-cnt_odd[l])/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>

using namespace std;

vector<int> G[100000];

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int X;
        cin >> X;
        G[X%M].push_back(X);
    }
    for(int i = 0; i < M; i++){
        sort(G[i].begin(), G[i].end());
    }
    int cnt_all[100000] = {0};
    int cnt_odd[100000] = {0};
    for(int i = 0; i < M; i++){
        if(G[i].size() == 0) continue;
        int prev = G[i][0];
        int cnt_cur = 1;
        cnt_all[i] = G[i].size();
        for(int j = 1; j < G[i].size(); j++){
            //cout << j << endl;
            if(prev == G[i][j]){
                cnt_cur++;
            }else{
                if(cnt_cur%2 == 1)cnt_odd[i]++;
                prev = G[i][j];
                cnt_cur = 1;
            }
        }
    }
    int ans = G[0].size()/2;
    if(M%2 == 0) ans += G[M/2].size()/2;
    for(int i = 1; 2*i < M; i++){
        int k, l;
        if(G[i].size() < G[M-i].size()){
            k = i;
            l = M-i;
        }else{
            k = M-i;
            l = i;
        }
        if((G[l].size() - G[k].size()) <= cnt_all[l]-cnt_odd[l]){
            ans += G[k].size() + (G[l].size() - G[k].size())/2;
        }else{
            ans += G[k].size() + (cnt_all[l]-cnt_odd[l])/2;
        }
    }
    cout << ans << endl;
}
```