#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
ll N; int M, Q; int A[101010];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//-----------------------------------------------------------------------------------
int B[1010101][7];
int simulate(int loop) {
    rep(i, 0, M * loop) {
        int y = i / 7;
        int x = i % 7;
        if(!A[i % M]) B[y][x] = 0;
        else B[y][x] = -1;
    }

    rep(i, M * loop, M * loop + 10) {
        int y = i / 7;
        int x = i % 7;
        B[y][x] = -1;
    }

    int cnt = 0;
    rep(i, 0, M * loop) {
        int y = i / 7;
        int x = i % 7;
        if (B[y][x] == 0) {
            cnt++;
            queue<int> que;
            que.push(i);
            while (!que.empty()) {
                int ii = que.front(); que.pop();
                int y = ii / 7;
                int x = ii % 7;
                if (B[y][x] != 0) continue;
                B[y][x] = cnt;
                rep(j, 0, 4) {
                    int yy = y + dy[j];
                    int xx = x + dx[j];
                    if (yy < 0) continue;
                    if (xx < 0 || 7 <= xx) continue;
                    if (B[yy][xx] == 0) {
                        que.push(yy * 7 + xx);
                    }
                }
            }
        }
    }

    return cnt;
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M >> Q;
    rep(i, 0, Q) {
        int a; cin >> a; A[a] = 1;
    }

    int loop = 1;
    if (M % 7) loop = 7;
    ll num = simulate(loop);
    
    ll k = N * 7 / (1LL * M * loop);
    if (k == 1) {
        cout << num << endl;
        return 0;
    }

    ll num2 = simulate(loop * 2);
    ll ans = num + (k - 1) * (num2 - num);
    cout << ans << endl;
}
### 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>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
ll N; int M, Q; int A[101010];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//-----------------------------------------------------------------------------------
int B[1010101][7];
int simulate(int loop) {
    rep(i, 0, M * loop) {
        int y = i / 7;
        int x = i % 7;
        if(!A[i % M]) B[y][x] = 0;
        else B[y][x] = -1;
    }

    rep(i, M * loop, M * loop + 10) {
        int y = i / 7;
        int x = i % 7;
        B[y][x] = -1;
    }

    int cnt = 0;
    rep(i, 0, M * loop) {
        int y = i / 7;
        int x = i % 7;
        if (B[y][x] == 0) {
            cnt++;
            queue<int> que;
            que.push(i);
            while (!que.empty()) {
                int ii = que.front(); que.pop();
                int y = ii / 7;
                int x = ii % 7;
                if (B[y][x] != 0) continue;
                B[y][x] = cnt;
                rep(j, 0, 4) {
                    int yy = y + dy[j];
                    int xx = x + dx[j];
                    if (yy < 0) continue;
                    if (xx < 0 || 7 <= xx) continue;
                    if (B[yy][xx] == 0) {
                        que.push(yy * 7 + xx);
                    }
                }
            }
        }
    }

    return cnt;
}
//-----------------------------------------------------------------------------------
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M >> Q;
    rep(i, 0, Q) {
        int a; cin >> a; A[a] = 1;
    }

    int loop = 1;
    if (M % 7) loop = 7;
    ll num = simulate(loop);
    
    ll k = N * 7 / (1LL * M * loop);
    if (k == 1) {
        cout << num << endl;
        return 0;
    }

    ll num2 = simulate(loop * 2);
    ll ans = num + (k - 1) * (num2 - num);
    cout << ans << endl;
}
```