#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};





struct UnionFind{
    vector<int> par, rank;

    void init(int n){
        par.resize(n);
        rank.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }

    int find(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=find(par[x]);
        }
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};


int main(){
    LL n,m,q;cin >> n >> m >> q;
    vector<int> a(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i];
    }
    LL t = 7 * n / m;
    vector<vector<int>> v(m, vector<int> (7,0));
    vector<vector<int>> vv(2 * m, vector<int> (7,0));
    vector<vector<int>> va(m/7, vector<int> (7,0));
    vector<vector<int>> vb(2*m/7, vector<int> (7,0));
    for (int i = 0; i < q; i++) {
        int y = a[i] / 7, x = a[i] % 7;
        if(m % 7 == 0){
            va[y][x] = 1;
            vb[y][x] = 1;
            vb[m / 7 + y][x] = 1;
        }
        else{
            for (int j = 0; j < 7; j++) {
                y = (a[i] + m * j) / 7, x = (a[i] + m * j) % 7;
                v[y][x] = 1;
                vv[y][x] = 1;
                vv[y+m][x] = 1;
            }
        }
    }
    auto f = [](vector<vector<int>> &a){
        int h = a.size(), w = a[0].size();
        UnionFind uf;
        uf.init(h*w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(j+1<w && a[i][j] == a[i][j+1]) uf.unite(i*7+j,i*7+j+1);
                if(i+1<h && a[i][j] == a[i+1][j]) uf.unite(i*7+j,(i+1)*7+j);
            }
        }
        int ret = 0;
        for (int i = 0; i < h*w; i++) {
            if(uf.find(i) == i && a[i/7][i%7] == 0) ret++;
        }
        return ret;
    };
    if(m%7==0){
        if(t == 1){
            cout << f(va) << endl;
        }
        else if(t == 2){
            cout << f(vb) << endl;
        }
        else{
            cout << f(va) + (t - 1) * (f(vb) - f(va)) << endl;
        }
    }
    else{
        t = n / m;
        if(t == 1){
            cout << f(v) << endl;
        }
        else if(t == 2){
            cout << f(vv) << endl;
        }
        else{
            cout << f(v) + (t - 1) * (f(vv) - f(v)) << endl;
        }
    }
    return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q


Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.



Sample Input 1


7 7 3
1 3 5


Sample Output 1


4


The calendar looks like this:


<image>

Sample Input 2


10 14 8
5 6 7 8 9 10 11 12


Sample Output 2


10


The calendar looks like this:


<image>

Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q

Examples

Input

7 7 3
1 3 5


Output

4


Input

10 14 8
5 6 7 8 9 10 11 12


Output

10

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};





struct UnionFind{
    vector<int> par, rank;

    void init(int n){
        par.resize(n);
        rank.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }

    int find(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=find(par[x]);
        }
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};


int main(){
    LL n,m,q;cin >> n >> m >> q;
    vector<int> a(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i];
    }
    LL t = 7 * n / m;
    vector<vector<int>> v(m, vector<int> (7,0));
    vector<vector<int>> vv(2 * m, vector<int> (7,0));
    vector<vector<int>> va(m/7, vector<int> (7,0));
    vector<vector<int>> vb(2*m/7, vector<int> (7,0));
    for (int i = 0; i < q; i++) {
        int y = a[i] / 7, x = a[i] % 7;
        if(m % 7 == 0){
            va[y][x] = 1;
            vb[y][x] = 1;
            vb[m / 7 + y][x] = 1;
        }
        else{
            for (int j = 0; j < 7; j++) {
                y = (a[i] + m * j) / 7, x = (a[i] + m * j) % 7;
                v[y][x] = 1;
                vv[y][x] = 1;
                vv[y+m][x] = 1;
            }
        }
    }
    auto f = [](vector<vector<int>> &a){
        int h = a.size(), w = a[0].size();
        UnionFind uf;
        uf.init(h*w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(j+1<w && a[i][j] == a[i][j+1]) uf.unite(i*7+j,i*7+j+1);
                if(i+1<h && a[i][j] == a[i+1][j]) uf.unite(i*7+j,(i+1)*7+j);
            }
        }
        int ret = 0;
        for (int i = 0; i < h*w; i++) {
            if(uf.find(i) == i && a[i/7][i%7] == 0) ret++;
        }
        return ret;
    };
    if(m%7==0){
        if(t == 1){
            cout << f(va) << endl;
        }
        else if(t == 2){
            cout << f(vb) << endl;
        }
        else{
            cout << f(va) + (t - 1) * (f(vb) - f(va)) << endl;
        }
    }
    else{
        t = n / m;
        if(t == 1){
            cout << f(v) << endl;
        }
        else if(t == 2){
            cout << f(vv) << endl;
        }
        else{
            cout << f(v) + (t - 1) * (f(vv) - f(v)) << endl;
        }
    }
    return 0;
}

```