#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i < n; i++)
#define repv(i,n) for(int i = n-1; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;

char BUF[3500000];
inline void I(int&a){scanf("%d",&a);}
inline void I(int&a,int&b){scanf("%d%d",&a,&b);}
inline void I(int&a,int&b,int&c){scanf("%d%d%d",&a,&b,&c);}
inline void I(int&a,int&b,int&c,int&d){scanf("%d%d%d%d",&a,&b,&c,&d);}
inline void L(ll&a){scanf("%lld",&a);}
inline void L(ll&a,ll&b){scanf("%lld%lld",&a,&b);}
inline void L(ll&a,ll&b,ll&c){scanf("%lld%lld%lld",&a,&b,&c);}
inline void L(ll&a,ll&b,ll&c,ll&d){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
inline void S(string&str){str.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)str.pb(BUF[i]);}
inline void SV(vector<int>&v){v.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)if('a'<=BUF[i]&&BUF[i]<='z')v.pb(BUF[i]-'a');else v.pb(BUF[i]-'A');}

const auto EPS = 1e-10;
const auto INF = 100000000;
const auto MOD = 1000000007;
typedef pair<ll,ll> P;

ll n;
int m, q;
int a[100000];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool b[7][100000], c[7][200000];

ll dfs1(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!b[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(b[xx][yy]) continue;
                    b[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

ll dfs2(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!c[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(c[xx][yy]) continue;
                    c[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

int main(){
    L(n); I(m,q);
    rep(i,q) I(a[i]);
    if(m%7 == 0){
        rep(i,q){
            b[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7+m/7] = true;
        }
        ll x = dfs1(m/7);
        ll y = dfs2(2*m/7);
        cout << x+(y-x)*(7*n/m-1) << endl;
    } else{
        rep(i,q){
            rep(j,7){
                int tmp = a[i]+m*j;
                b[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7+m] = true;
            }
        }
        ll x = dfs1(m);
        ll y = dfs2(2*m);
        cout << x+(y-x)*(n/m-1) << endl;
    }
}































### 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>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i < n; i++)
#define repv(i,n) for(int i = n-1; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;

char BUF[3500000];
inline void I(int&a){scanf("%d",&a);}
inline void I(int&a,int&b){scanf("%d%d",&a,&b);}
inline void I(int&a,int&b,int&c){scanf("%d%d%d",&a,&b,&c);}
inline void I(int&a,int&b,int&c,int&d){scanf("%d%d%d%d",&a,&b,&c,&d);}
inline void L(ll&a){scanf("%lld",&a);}
inline void L(ll&a,ll&b){scanf("%lld%lld",&a,&b);}
inline void L(ll&a,ll&b,ll&c){scanf("%lld%lld%lld",&a,&b,&c);}
inline void L(ll&a,ll&b,ll&c,ll&d){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
inline void S(string&str){str.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)str.pb(BUF[i]);}
inline void SV(vector<int>&v){v.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)if('a'<=BUF[i]&&BUF[i]<='z')v.pb(BUF[i]-'a');else v.pb(BUF[i]-'A');}

const auto EPS = 1e-10;
const auto INF = 100000000;
const auto MOD = 1000000007;
typedef pair<ll,ll> P;

ll n;
int m, q;
int a[100000];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool b[7][100000], c[7][200000];

ll dfs1(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!b[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(b[xx][yy]) continue;
                    b[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

ll dfs2(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!c[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(c[xx][yy]) continue;
                    c[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

int main(){
    L(n); I(m,q);
    rep(i,q) I(a[i]);
    if(m%7 == 0){
        rep(i,q){
            b[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7+m/7] = true;
        }
        ll x = dfs1(m/7);
        ll y = dfs2(2*m/7);
        cout << x+(y-x)*(7*n/m-1) << endl;
    } else{
        rep(i,q){
            rep(j,7){
                int tmp = a[i]+m*j;
                b[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7+m] = true;
            }
        }
        ll x = dfs1(m);
        ll y = dfs2(2*m);
        cout << x+(y-x)*(n/m-1) << endl;
    }
}































```