/***********************************************
#
#      Filename: c.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-19 23:53:20
***********************************************/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int m, q;
bool vis[100000 + 10];
bool bao[1000000 + 10][7];
bool used[1000000 + 10][7];

void paint(int base, int mm) {
    for (int i = 0; i < mm; ++ i) {
        if (vis[i % m]) {
            int r = i / 7;
            int c = i % 7;
            bao[r + base][c] = true;
        }
    }
}

int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
void dfs(int x, int y, int rmax) {
    used[x][y] = true;
    for (int i = 0; i < 4; ++ i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx>=0 && nx<rmax && ny>=0 && ny<7 && !used[nx][ny] && !bao[nx][ny]) {
            dfs(nx, ny, rmax);
        }
    }
}

int main()
{
    cin >> n >> m >> q;
    int r;
    for (int i = 0; i < q; ++ i) {
        cin >> r;
        vis[r] = true;
    }

    int mm = m;
    if (m % 7) mm *= 7;

    paint(0, mm);
    int count1 = 0;
    for (int i = 0; i < mm/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, mm/7);
                ++ count1;
            }
        }
    }

    paint(mm/7, mm);
    int count2 = 0;
    memset(used, false, sizeof(used));
    for (int i = 0; i < 2*mm/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, 2*mm/7);
                ++ count2;
            }
        }
    }

    cout << count1 * 1L + (count2 - count1) * 1L * (n / (mm/7) - 1L) << endl;
    return 0;
}

### Prompt

Please create a solution in CPP 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
/***********************************************
#
#      Filename: c.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-19 23:53:20
***********************************************/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int m, q;
bool vis[100000 + 10];
bool bao[1000000 + 10][7];
bool used[1000000 + 10][7];

void paint(int base, int mm) {
    for (int i = 0; i < mm; ++ i) {
        if (vis[i % m]) {
            int r = i / 7;
            int c = i % 7;
            bao[r + base][c] = true;
        }
    }
}

int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
void dfs(int x, int y, int rmax) {
    used[x][y] = true;
    for (int i = 0; i < 4; ++ i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx>=0 && nx<rmax && ny>=0 && ny<7 && !used[nx][ny] && !bao[nx][ny]) {
            dfs(nx, ny, rmax);
        }
    }
}

int main()
{
    cin >> n >> m >> q;
    int r;
    for (int i = 0; i < q; ++ i) {
        cin >> r;
        vis[r] = true;
    }

    int mm = m;
    if (m % 7) mm *= 7;

    paint(0, mm);
    int count1 = 0;
    for (int i = 0; i < mm/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, mm/7);
                ++ count1;
            }
        }
    }

    paint(mm/7, mm);
    int count2 = 0;
    memset(used, false, sizeof(used));
    for (int i = 0; i < 2*mm/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, 2*mm/7);
                ++ count2;
            }
        }
    }

    cout << count1 * 1L + (count2 - count1) * 1L * (n / (mm/7) - 1L) << endl;
    return 0;
}

```