#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;
vector<vector<int>> state(MAX,vector<int>(7,0));

vector<int> dx={-1,0,0,1},dy={0,-1,1,0};

void DFS(int u,int v,int goal,int when){
    stack<pair<int,int>> ST;
    ST.push(make_pair(u,v));
    state[u][v]=when;
    
    while(!ST.empty()){
        int a=ST.top().first,b=ST.top().second;
        ST.pop();
        for(int i=0;i<4;i++){
            int c=a+dx[i],d=b+dy[i];
            if(c<0||c>=goal||d<0||d>=7) continue;
            if(state[c][d]==0){
                ST.push(make_pair(c,d));
                state[c][d]=when;
            }
        }
    }
}

int main(){
    
    ll N;
    int M,Q;cin>>N>>M>>Q;
    vector<int> A(Q);
    for(int i=0;i<Q;i++){
        cin>>A[i];
    }
    if(M%7==0){
        for(int i=0;i<Q;i++){
            int a=A[i]/7,b=A[i]%7;
            state[a][b]=-1;
        }
        int now=0;
        for(int i=0;i<M/7;i++){
            for(int j=0;j<7;j++){
                if(state[i][j]==0){
                    now++;
                    DFS(i,j,M/7,now);
                }
            }
        }
        set<pair<int,int>> se;
        for(int j=0;j<7;j++){
            if(state[0][j]>=0&&state[M/7-1][j]>=0) se.insert(make_pair(state[0][j],state[M/7-1][j]));
        }
        
        cout<<7*N/M*now-(7*N/M-1)*se.size()<<endl;
    }else{
        for(int i=0;i<Q;i++){
            for(int j=0;j<7;j++){
                int a=(A[i]+M*j)/7,b=(A[i]+M*j)%7;
                state[a][b]=-1;
            }
        }
        int now=0;
        for(int i=0;i<M;i++){
            for(int j=0;j<7;j++){
                if(state[i][j]==0){
                    now++;
                    DFS(i,j,M,now);
                }
            }
        }
        set<pair<int,int>> se;
        for(int j=0;j<7;j++){
            if(state[0][j]>=0&&state[M-1][j]>=0) se.insert(make_pair(state[0][j],state[M-1][j]));
        }
        
        cout<<N/M*now-(N/M-1)*se.size()<<endl;
    }
}



### Prompt

Develop a solution in cpp to the problem described below:

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;
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;
vector<vector<int>> state(MAX,vector<int>(7,0));

vector<int> dx={-1,0,0,1},dy={0,-1,1,0};

void DFS(int u,int v,int goal,int when){
    stack<pair<int,int>> ST;
    ST.push(make_pair(u,v));
    state[u][v]=when;
    
    while(!ST.empty()){
        int a=ST.top().first,b=ST.top().second;
        ST.pop();
        for(int i=0;i<4;i++){
            int c=a+dx[i],d=b+dy[i];
            if(c<0||c>=goal||d<0||d>=7) continue;
            if(state[c][d]==0){
                ST.push(make_pair(c,d));
                state[c][d]=when;
            }
        }
    }
}

int main(){
    
    ll N;
    int M,Q;cin>>N>>M>>Q;
    vector<int> A(Q);
    for(int i=0;i<Q;i++){
        cin>>A[i];
    }
    if(M%7==0){
        for(int i=0;i<Q;i++){
            int a=A[i]/7,b=A[i]%7;
            state[a][b]=-1;
        }
        int now=0;
        for(int i=0;i<M/7;i++){
            for(int j=0;j<7;j++){
                if(state[i][j]==0){
                    now++;
                    DFS(i,j,M/7,now);
                }
            }
        }
        set<pair<int,int>> se;
        for(int j=0;j<7;j++){
            if(state[0][j]>=0&&state[M/7-1][j]>=0) se.insert(make_pair(state[0][j],state[M/7-1][j]));
        }
        
        cout<<7*N/M*now-(7*N/M-1)*se.size()<<endl;
    }else{
        for(int i=0;i<Q;i++){
            for(int j=0;j<7;j++){
                int a=(A[i]+M*j)/7,b=(A[i]+M*j)%7;
                state[a][b]=-1;
            }
        }
        int now=0;
        for(int i=0;i<M;i++){
            for(int j=0;j<7;j++){
                if(state[i][j]==0){
                    now++;
                    DFS(i,j,M,now);
                }
            }
        }
        set<pair<int,int>> se;
        for(int j=0;j<7;j++){
            if(state[0][j]>=0&&state[M-1][j]>=0) se.insert(make_pair(state[0][j],state[M-1][j]));
        }
        
        cout<<N/M*now-(N/M-1)*se.size()<<endl;
    }
}



```