#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define rFORq(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
const ll p = 1000000007;
ll dx[4] = {-7,-1,1,7};
ll N,M,Q;
static ll a[100002] = {};
static bool grid[700003] = {};
static bool visited[1500003] = {};
static bool visited2[1500003] = {};

void dfs0(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 7*N) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs0(next);
    }

    return;
}

void dfs1(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs1(next);
    }

    return;
}

void dfs2(ll pos){
    if (visited2[pos]) return;
    visited2[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 2*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited2[next]) continue;
        dfs2(next);
    }

    return;
}

void dfs3(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 7*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs3(next);
    }

    return;
}
void dfs4(ll pos){
    if (visited2[pos]) return;
    visited2[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 14*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next % M]) continue;
        if (visited2[next]) continue;
        dfs4(next);
    }

    return;
}

void solve1(){
    ll count = 0;
    FORq(i,0,7*N-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs0(i);
            count++;
        }
    }

    PRINTLLD(count);
    return;
}


void solve23(){
    ll count1 = 0;
    ll count2 = 0;

    FORq(i,0,M-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs1(i);
            count1++;
        }
    }
    //printf("count1 = %lld\n",count1);

    FORq(i,0,2*M-1){
        if ((grid[i] == false) and (visited2[i] == false)){
            dfs2(i);
            count2++;
        }
    }

    //printf("count2 = %lld\n",count2);
    ll A,B;
    A = count2 - count1;
    B = count1 - A;
    ll c = 7*N / M;
    PRINTLLD(A*c + B);
    return;
}

void solve4(){
    ll count1 = 0;
    ll count2 = 0;
    FORq(i,0,7*M-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs3(i);
            count1++;
        }
    }
    //printf("count1 = %lld\n",count1);

    FORq(i,0,14*M-1){
        if ((grid[i % M] == false) and (visited2[i] == false)){
            dfs4(i);
            count2++;
        }
    }

    ll A,B; A = count2 - count1;
    B = count1 - A;
    ll x = N/M;
    PRINTLLD(A*x + B);
}


int main(){
    SCLLD3(N,M,Q);
    ARSCD(a,Q);

    REP(q,Q){
        ll ai = a[q];
        ll k = 0;
        while(k*M + ai <= 700000 + 2 ){
            grid[k*M+ai] = true;
            k++;
        }
    }

    if (N <= 100000){ // #1
        solve1();
    } else if (M % 7 == 0){
        solve23();
    } else {
        solve4();
    }
}

### Prompt

In cpp, your task is to solve 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>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define rFORq(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
const ll p = 1000000007;
ll dx[4] = {-7,-1,1,7};
ll N,M,Q;
static ll a[100002] = {};
static bool grid[700003] = {};
static bool visited[1500003] = {};
static bool visited2[1500003] = {};

void dfs0(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 7*N) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs0(next);
    }

    return;
}

void dfs1(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs1(next);
    }

    return;
}

void dfs2(ll pos){
    if (visited2[pos]) return;
    visited2[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 2*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited2[next]) continue;
        dfs2(next);
    }

    return;
}

void dfs3(ll pos){
    if (visited[pos]) return;
    visited[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 7*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next]) continue;
        if (visited[next]) continue;
        dfs3(next);
    }

    return;
}
void dfs4(ll pos){
    if (visited2[pos]) return;
    visited2[pos] = true;

    REP(k,4){
        ll next = pos + dx[k];
        if (next >= 14*M) continue;
        if (next < 0) continue;
        if ((k==1) and (pos % 7 == 0)) continue;
        if ((k==2) and (pos % 7 == 6)) continue;
        if (grid[next % M]) continue;
        if (visited2[next]) continue;
        dfs4(next);
    }

    return;
}

void solve1(){
    ll count = 0;
    FORq(i,0,7*N-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs0(i);
            count++;
        }
    }

    PRINTLLD(count);
    return;
}


void solve23(){
    ll count1 = 0;
    ll count2 = 0;

    FORq(i,0,M-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs1(i);
            count1++;
        }
    }
    //printf("count1 = %lld\n",count1);

    FORq(i,0,2*M-1){
        if ((grid[i] == false) and (visited2[i] == false)){
            dfs2(i);
            count2++;
        }
    }

    //printf("count2 = %lld\n",count2);
    ll A,B;
    A = count2 - count1;
    B = count1 - A;
    ll c = 7*N / M;
    PRINTLLD(A*c + B);
    return;
}

void solve4(){
    ll count1 = 0;
    ll count2 = 0;
    FORq(i,0,7*M-1){
        if ((grid[i] == false) and (visited[i] == false)){
            dfs3(i);
            count1++;
        }
    }
    //printf("count1 = %lld\n",count1);

    FORq(i,0,14*M-1){
        if ((grid[i % M] == false) and (visited2[i] == false)){
            dfs4(i);
            count2++;
        }
    }

    ll A,B; A = count2 - count1;
    B = count1 - A;
    ll x = N/M;
    PRINTLLD(A*x + B);
}


int main(){
    SCLLD3(N,M,Q);
    ARSCD(a,Q);

    REP(q,Q){
        ll ai = a[q];
        ll k = 0;
        while(k*M + ai <= 700000 + 2 ){
            grid[k*M+ai] = true;
            k++;
        }
    }

    if (N <= 100000){ // #1
        solve1();
    } else if (M % 7 == 0){
        solve23();
    } else {
        solve4();
    }
}

```