#include<iostream>
#include<cstdio>
using namespace std;

long long n, m, q, a[200000];
bool is_black[200000][7];
bool visited_1[200000][7];
bool visited_2[200000][7];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};


void visit_1(int r, int c){
    visited_1[r][c] = true;
    for(int i = 0; i < 4; i++){
        int r_ = r + dx[i];
        int c_ = c + dy[i];
        if(r_ >= 0 && r_ < m/7 && c_ >= 0 && c_ < 7 && (!is_black[r_][c_]) && (!visited_1[r_][c_])){
            visit_1(r_, c_);
        }
    }
}

void visit_2(int r, int c){
    visited_2[r][c] = true;
    for(int i = 0; i < 4; i++){
        int r_ = r + dx[i];
        int c_ = c + dy[i];
        if(r_ >= 0 && r_ < 2*m/7 && c_ >= 0 && c_ < 7 && (!is_black[r_][c_]) && (!visited_2[r_][c_])){
            visit_2(r_, c_);
        }
    }
}

int main(){
    cin >> n >> m >> q;
    if(m % 7 == 0){
    for(int i = 0; i < q; i++){
        cin >> a[i];
        is_black[a[i] / 7][a[i] % 7] = true;
        is_black[(a[i]+m)/7][a[i]%7] = true;
    }
    }else{
        m *= 7;
        for(int i = 0; i < q; i++){
            cin >> a[i];
            for(int j = 0; j < 7; j++){
                is_black[(a[i] + j*m/7)/7][(a[i]+j*m/7)%7] = true;
                is_black[(a[i] + j*m/7 + m)/7][(a[i]+j*m/7)%7] = true;
            }
        }
    }
    long long cnt_1 = 0;
    for(int i = 0; i < m/7; i++){
        for(int j = 0; j < 7; j++){
            if(!visited_1[i][j] && !is_black[i][j]){
                visit_1(i, j);
                cnt_1++;
            }
        }
    }

    long long cnt_2 = 0;
    for(int i = 0; i < 2*m/7; i++){
        for(int j = 0; j < 7; j++){
            if(!visited_2[i][j] && !is_black[i][j]){
                visit_2(i, j);
                cnt_2++;
            }
        }
    }

    cout << (cnt_2 - cnt_1) * (7 * n / m) + (2*cnt_1 - cnt_2) << endl;
    //cout << cnt_1 << endl;
    //cout << cnt_2 << endl;
    
}
### Prompt

Create a solution in cpp for 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<iostream>
#include<cstdio>
using namespace std;

long long n, m, q, a[200000];
bool is_black[200000][7];
bool visited_1[200000][7];
bool visited_2[200000][7];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};


void visit_1(int r, int c){
    visited_1[r][c] = true;
    for(int i = 0; i < 4; i++){
        int r_ = r + dx[i];
        int c_ = c + dy[i];
        if(r_ >= 0 && r_ < m/7 && c_ >= 0 && c_ < 7 && (!is_black[r_][c_]) && (!visited_1[r_][c_])){
            visit_1(r_, c_);
        }
    }
}

void visit_2(int r, int c){
    visited_2[r][c] = true;
    for(int i = 0; i < 4; i++){
        int r_ = r + dx[i];
        int c_ = c + dy[i];
        if(r_ >= 0 && r_ < 2*m/7 && c_ >= 0 && c_ < 7 && (!is_black[r_][c_]) && (!visited_2[r_][c_])){
            visit_2(r_, c_);
        }
    }
}

int main(){
    cin >> n >> m >> q;
    if(m % 7 == 0){
    for(int i = 0; i < q; i++){
        cin >> a[i];
        is_black[a[i] / 7][a[i] % 7] = true;
        is_black[(a[i]+m)/7][a[i]%7] = true;
    }
    }else{
        m *= 7;
        for(int i = 0; i < q; i++){
            cin >> a[i];
            for(int j = 0; j < 7; j++){
                is_black[(a[i] + j*m/7)/7][(a[i]+j*m/7)%7] = true;
                is_black[(a[i] + j*m/7 + m)/7][(a[i]+j*m/7)%7] = true;
            }
        }
    }
    long long cnt_1 = 0;
    for(int i = 0; i < m/7; i++){
        for(int j = 0; j < 7; j++){
            if(!visited_1[i][j] && !is_black[i][j]){
                visit_1(i, j);
                cnt_1++;
            }
        }
    }

    long long cnt_2 = 0;
    for(int i = 0; i < 2*m/7; i++){
        for(int j = 0; j < 7; j++){
            if(!visited_2[i][j] && !is_black[i][j]){
                visit_2(i, j);
                cnt_2++;
            }
        }
    }

    cout << (cnt_2 - cnt_1) * (7 * n / m) + (2*cnt_1 - cnt_2) << endl;
    //cout << cnt_1 << endl;
    //cout << cnt_2 << endl;
    
}
```