#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9,MOD = 1e9+7,ohara = 1e6;
const ll LINF = 1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,q,grid[ohara][10],aa;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl,mem[ohara][10];
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

void dfs1(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<n&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs1(ny,nx);
        }
    }
}

ll solve1(){
    ll ret=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,n){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,n){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret++;
                dfs1(i,j);
            }
        }
    }
    return ret;
}

void dfs2(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m/7&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs2(ny,nx);
        }
    }
}

void dfs3(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m/7+m/7&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs3(ny,nx);
        }
    }
}

ll solve2(){
    ll ret1=0,ret2=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,m/7){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m/7){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret1++;
                dfs2(i,j);
            }
        }
    }
    rep(i,m/7){
        rep(j,7){
            mem[i][j]=false;
        }
    }
    rrep(i,m/7,m/7+m/7){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m/7+m/7){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret2++;
                dfs3(i,j);
            }
        }
    }
    aa=ret2-ret1;
    b=ret1-aa;
    ll kaisuu;
    kaisuu=n/(m/7);
    return aa*kaisuu+b;
}

void dfs4(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs4(ny,nx);
        }
    }
}

void dfs5(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m+m&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs5(ny,nx);
        }
    }
}

ll solve3(){
    ll ret1=0,ret2=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,m){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret1++;
                dfs4(i,j);
            }
        }
    }
    rep(i,m){
        rep(j,7){
            mem[i][j]=false;
        }
    }
    rrep(i,m,m+m){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m+m){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret2++;
                dfs5(i,j);
            }
        }
    }
    aa=ret2-ret1;
    b=ret1-aa;
    ll kaisuu;
    kaisuu=n/(m);
    return aa*kaisuu+b;
}

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>m>>q;
    rep(i,q)cin>>a[i];
    if(n<=100000)ans=solve1();
    else if(m%7==0)ans=solve2();
    else ans=solve3();
    Cout(ans);
    return 0;
}

### Prompt

Your task is to create 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>
typedef long long ll;
const int INF = 1e9,MOD = 1e9+7,ohara = 1e6;
const ll LINF = 1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,q,grid[ohara][10],aa;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl,mem[ohara][10];
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

void dfs1(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<n&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs1(ny,nx);
        }
    }
}

ll solve1(){
    ll ret=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,n){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,n){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret++;
                dfs1(i,j);
            }
        }
    }
    return ret;
}

void dfs2(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m/7&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs2(ny,nx);
        }
    }
}

void dfs3(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m/7+m/7&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs3(ny,nx);
        }
    }
}

ll solve2(){
    ll ret1=0,ret2=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,m/7){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m/7){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret1++;
                dfs2(i,j);
            }
        }
    }
    rep(i,m/7){
        rep(j,7){
            mem[i][j]=false;
        }
    }
    rrep(i,m/7,m/7+m/7){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m/7+m/7){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret2++;
                dfs3(i,j);
            }
        }
    }
    aa=ret2-ret1;
    b=ret1-aa;
    ll kaisuu;
    kaisuu=n/(m/7);
    return aa*kaisuu+b;
}

void dfs4(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs4(ny,nx);
        }
    }
}

void dfs5(ll i,ll j){
    mem[i][j]=true;
    rep(k,4){
        int nx=j+dx[k],ny=i+dy[k];
        if(nx>=0&&nx<7&&ny>=0&&ny<m+m&&!mem[ny][nx]&&!grid[ny][nx]){
            dfs5(ny,nx);
        }
    }
}

ll solve3(){
    ll ret1=0,ret2=0;
    map<ll,ll> out;
    rep(i,q)out[a[i]]=1;
    rep(i,m){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret1++;
                dfs4(i,j);
            }
        }
    }
    rep(i,m){
        rep(j,7){
            mem[i][j]=false;
        }
    }
    rrep(i,m,m+m){
        rep(j,7){
            pos=7*i+j;
            if(out[pos%m]==1){
                grid[i][j]=1;
            }
        }
    }
    rep(i,m+m){
        rep(j,7){
            if(!mem[i][j]&&!grid[i][j]){
                ret2++;
                dfs5(i,j);
            }
        }
    }
    aa=ret2-ret1;
    b=ret1-aa;
    ll kaisuu;
    kaisuu=n/(m);
    return aa*kaisuu+b;
}

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>m>>q;
    rep(i,q)cin>>a[i];
    if(n<=100000)ans=solve1();
    else if(m%7==0)ans=solve2();
    else ans=solve3();
    Cout(ans);
    return 0;
}

```