#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

ll n;
int m,q;
int a[125252];

int mp[125252][7];
int dat[125252*7];
void init(){
  REP(i,125252*7)dat[i]=-1;
}
int root(int x){
  return dat[x]<0?x:dat[x]=root(dat[x]);
}
void unite(int a,int b){
  a=root(a);
  b=root(b);
  if(a!=b){
    if(dat[a]>dat[b])swap(a,b);
    dat[a]+=dat[b];
    dat[b]=a;
  }
}

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main(){
  scanf("%lld%d%d",&n,&m,&q);
  REP(i,q)scanf("%d",a+i);
  ll u = (m%7==0) ? (m/7) : m;
  ll k = n / u;
  // solve u,m,q
  REP(i,q){
    int v = a[i];
    while(v < 7*u){
      mp[v/7][v%7] = 1;
      v += m;
    }
  }
  init();
  REP(i,u)REP(j,7){
    if(mp[i][j])continue;
    int id = i*7 + j;
    REP(d,4){
      int ni = i+dy[d];
      int nj = j+dx[d];
      if(ni<0 || nj<0 || ni>=u || nj>=7)continue;
      if(mp[ni][nj])continue;
      unite(id,ni*7+nj);
    }
  }
  ll subans = 0;
  REP(i,u)REP(j,7)if(!mp[i][j] && root(7*i+j)==7*i+j)subans++;
  // merge
  set<pii> S;
  REP(i,7){
    if(mp[0][i] || mp[u-1][i])continue;
    int ida = root(i);
    int idb = root(7*(u-1) + i);
    pii P = pii(ida,idb);
    S.insert(P);
  }
  ll yo = S.size();
  ll ans = subans * k - yo * (k-1);
  printf("%lld\n",ans);
  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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

ll n;
int m,q;
int a[125252];

int mp[125252][7];
int dat[125252*7];
void init(){
  REP(i,125252*7)dat[i]=-1;
}
int root(int x){
  return dat[x]<0?x:dat[x]=root(dat[x]);
}
void unite(int a,int b){
  a=root(a);
  b=root(b);
  if(a!=b){
    if(dat[a]>dat[b])swap(a,b);
    dat[a]+=dat[b];
    dat[b]=a;
  }
}

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main(){
  scanf("%lld%d%d",&n,&m,&q);
  REP(i,q)scanf("%d",a+i);
  ll u = (m%7==0) ? (m/7) : m;
  ll k = n / u;
  // solve u,m,q
  REP(i,q){
    int v = a[i];
    while(v < 7*u){
      mp[v/7][v%7] = 1;
      v += m;
    }
  }
  init();
  REP(i,u)REP(j,7){
    if(mp[i][j])continue;
    int id = i*7 + j;
    REP(d,4){
      int ni = i+dy[d];
      int nj = j+dx[d];
      if(ni<0 || nj<0 || ni>=u || nj>=7)continue;
      if(mp[ni][nj])continue;
      unite(id,ni*7+nj);
    }
  }
  ll subans = 0;
  REP(i,u)REP(j,7)if(!mp[i][j] && root(7*i+j)==7*i+j)subans++;
  // merge
  set<pii> S;
  REP(i,7){
    if(mp[0][i] || mp[u-1][i])continue;
    int ida = root(i);
    int idb = root(7*(u-1) + i);
    pii P = pii(ida,idb);
    S.insert(P);
  }
  ll yo = S.size();
  ll ans = subans * k - yo * (k-1);
  printf("%lld\n",ans);
  return 0;
}

```