#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

vector<int> uf, usz;
int nc;

void init(int n){
  vector<int> uf_(n);
  vector<int> usz_(n, 1);
  uf = uf_;
  usz = usz_;
  nc = n;

  for(int i = 0; i < uf.size(); i++){
    uf[i] = i;
  }
}

int find(int a){
  return (uf[a] == a) ? a : uf[a] = find(uf[a]);
}

void union_(int a, int b){
  a = find(a);
  b = find(b);

  if(a != b){
    if(usz[a] >= usz[b]){
      swap(a, b);
    }
    uf[a] = b;
    usz[b] += usz[a];
    nc--;
  }
}

int check(int a, int b){
  return (find(a) == find(b)) ? 1 : 0;
}

int get_size(int a){
  return usz[find(a)];
}

ll d[700100];

int main(){
	ll n,m,q;
	cin>>n>>m>>q;
	ll flag7 = 0;
	if(m%7!=0){
		flag7 = 1;
		m *= 7;
	}
	init(m+1);
	clr(d,0);
	vector<ll> v;
	rep(i,0,q){
		ll a;
		cin>>a;
		if(flag7==1){
			rep(j,0,7){
				d[a+(m/7)*j] = 1;
			}
		}
		else{
			d[a] = 1;
		}
	}
	rep(i,0,m){
		if(d[i]==1){
			union_(i,m);
			continue;
		}
		vector<ll> v1;
		if(i-7>=0)v1.pb(i-7);
		if(i%7!=0)v1.pb(i-1);
		if(i%7!=6)v1.pb(i+1);
		if(i+7<m)v1.pb(i+7);
		rep(j,0,v1.sz){
			if(d[v1[j]]==1)continue;
			union_(i,v1[j]);
		}
	}
	ll ans1 = nc-1;
	set<ll> se1;
	set<pair<ll,ll> > se2; 
	rep(i,0,7){
		if(d[i]==0&&d[m-7+i]==0){
			ll a1 = find(i);
			ll b1 = find(m-7+i);
			if(a1==b1)se1.insert(a1);
			else{
				se2.insert(mp(max(a1,b1),min(a1,b1)));
			}
		}
	}
	vector<ll> v1(all(se1));
	vector<pair<ll,ll> > v2(all(se2));
	ll ans2 = v1.sz;
	ll ans3 = v2.sz;
	ll ans4 = 0;
	rep(i,0,v2.sz){
		int flag = 1;
		rep(j,0,v1.sz){
			if(v1[j]==v2[i].fi||v1[j]==v2[i].se){
				flag = 0;
			}
		}
		if(flag == 0){
			ans3--;
			ans4++;
		}
	}
	ll a = 7*n/m;
	ans1 -= (ans2+ans4+ans3*2);
	cout << ans1*a+ans2+ans3*(a+1)+ans4 << endl;
	return 0;
}



### Prompt

Your challenge is to write 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 <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

vector<int> uf, usz;
int nc;

void init(int n){
  vector<int> uf_(n);
  vector<int> usz_(n, 1);
  uf = uf_;
  usz = usz_;
  nc = n;

  for(int i = 0; i < uf.size(); i++){
    uf[i] = i;
  }
}

int find(int a){
  return (uf[a] == a) ? a : uf[a] = find(uf[a]);
}

void union_(int a, int b){
  a = find(a);
  b = find(b);

  if(a != b){
    if(usz[a] >= usz[b]){
      swap(a, b);
    }
    uf[a] = b;
    usz[b] += usz[a];
    nc--;
  }
}

int check(int a, int b){
  return (find(a) == find(b)) ? 1 : 0;
}

int get_size(int a){
  return usz[find(a)];
}

ll d[700100];

int main(){
	ll n,m,q;
	cin>>n>>m>>q;
	ll flag7 = 0;
	if(m%7!=0){
		flag7 = 1;
		m *= 7;
	}
	init(m+1);
	clr(d,0);
	vector<ll> v;
	rep(i,0,q){
		ll a;
		cin>>a;
		if(flag7==1){
			rep(j,0,7){
				d[a+(m/7)*j] = 1;
			}
		}
		else{
			d[a] = 1;
		}
	}
	rep(i,0,m){
		if(d[i]==1){
			union_(i,m);
			continue;
		}
		vector<ll> v1;
		if(i-7>=0)v1.pb(i-7);
		if(i%7!=0)v1.pb(i-1);
		if(i%7!=6)v1.pb(i+1);
		if(i+7<m)v1.pb(i+7);
		rep(j,0,v1.sz){
			if(d[v1[j]]==1)continue;
			union_(i,v1[j]);
		}
	}
	ll ans1 = nc-1;
	set<ll> se1;
	set<pair<ll,ll> > se2; 
	rep(i,0,7){
		if(d[i]==0&&d[m-7+i]==0){
			ll a1 = find(i);
			ll b1 = find(m-7+i);
			if(a1==b1)se1.insert(a1);
			else{
				se2.insert(mp(max(a1,b1),min(a1,b1)));
			}
		}
	}
	vector<ll> v1(all(se1));
	vector<pair<ll,ll> > v2(all(se2));
	ll ans2 = v1.sz;
	ll ans3 = v2.sz;
	ll ans4 = 0;
	rep(i,0,v2.sz){
		int flag = 1;
		rep(j,0,v1.sz){
			if(v1[j]==v2[i].fi||v1[j]==v2[i].se){
				flag = 0;
			}
		}
		if(flag == 0){
			ans3--;
			ans4++;
		}
	}
	ll a = 7*n/m;
	ans1 -= (ans2+ans4+ans3*2);
	cout << ans1*a+ans2+ans3*(a+1)+ans4 << endl;
	return 0;
}



```