#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define I(i,j) (i*7+j)

ll n,m,q,a[100050];
bool g[3000000];
bool used[3000000];

void dfs1(ll n,ll i,ll j) {
    REP(k,4) {
        ll y = i + dy[k],x = j + dx[k];
        if(0 <= y && y < n && 0 <= x && x < 7 && !used[I(y,x)] && !g[I(y,x)]) {
            used[I(y,x)] = true;
            dfs1(n,y,x);
        }
    }
}

int main(){
    cin >> n >> m >> q;

    REP(i,q)
        cin >> a[i];

    ll l = 1;

    while(m * l % 7 != 0)l++;

    ll n2 = m * l / 7;

    REP(i,q) {
        ll p = a[i];

        while(p < n2 * 7){
            g[p] = true;
            p += m;
        }
    }

    ll c = 0;
    REP(i,n2) {
        REP(j,7) {
            if(!used[I(i,j)] && !g[I(i,j)]) {
                c++;
                used[I(i,j)] = true;
                dfs1(n2,i,j);
            }
        }
    }
    if(n == n2) {
        cout << c << endl;
        return 0;
    }

    REP(i,n2*7*2)
        g[i] = used[i] = false;

    REP(i,q) {
        ll p = a[i];

        while(p < n2 * 7 * 2){
            g[p] = true;
            p += m;
        }
    }

    ll c2 = 0;

    REP(i,n2*2) {
        REP(j,7) {
            if(!used[I(i,j)] && !g[I(i,j)]) {
                c2++;
                used[I(i,j)] = true;
                dfs1(n2*2,i,j);
            }
        }
    }

	ll b = 2 * c - c2;
	ll a = c - b;

	cout << a * n / n2 + b << endl;

    return 0;
}


### Prompt

Construct a Cpp code solution to the problem outlined:

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<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define I(i,j) (i*7+j)

ll n,m,q,a[100050];
bool g[3000000];
bool used[3000000];

void dfs1(ll n,ll i,ll j) {
    REP(k,4) {
        ll y = i + dy[k],x = j + dx[k];
        if(0 <= y && y < n && 0 <= x && x < 7 && !used[I(y,x)] && !g[I(y,x)]) {
            used[I(y,x)] = true;
            dfs1(n,y,x);
        }
    }
}

int main(){
    cin >> n >> m >> q;

    REP(i,q)
        cin >> a[i];

    ll l = 1;

    while(m * l % 7 != 0)l++;

    ll n2 = m * l / 7;

    REP(i,q) {
        ll p = a[i];

        while(p < n2 * 7){
            g[p] = true;
            p += m;
        }
    }

    ll c = 0;
    REP(i,n2) {
        REP(j,7) {
            if(!used[I(i,j)] && !g[I(i,j)]) {
                c++;
                used[I(i,j)] = true;
                dfs1(n2,i,j);
            }
        }
    }
    if(n == n2) {
        cout << c << endl;
        return 0;
    }

    REP(i,n2*7*2)
        g[i] = used[i] = false;

    REP(i,q) {
        ll p = a[i];

        while(p < n2 * 7 * 2){
            g[p] = true;
            p += m;
        }
    }

    ll c2 = 0;

    REP(i,n2*2) {
        REP(j,7) {
            if(!used[I(i,j)] && !g[I(i,j)]) {
                c2++;
                used[I(i,j)] = true;
                dfs1(n2*2,i,j);
            }
        }
    }

	ll b = 2 * c - c2;
	ll a = c - b;

	cout << a * n / n2 + b << endl;

    return 0;
}


```