#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
 
using namespace std;
 
#define int long long
//typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD = 1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int par[1400001];
int rnk[1400001];

void init(int n){
	for(int i = 0;i < n;i++){
		par[i] = i;
		rnk[i] = 0;
	}
}

int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int x,int y){
	return find(x) == find(y);
}

int n,m,q;
int a[100000];

bool fnd(int x){
	return upper_bound(a,a + q,x) - lower_bound(a,a + q,x);
}

signed main(){
	int n1,n2;
	cin >> n >> m >> q;
	init(m * 7);
	int nn,mm;
	if(m % 7 == 0){
		nn = n / (m / 7);
		mm = m / 7;
	}
	else{
		nn = n;
		mm = m;
	}
	for(int i = 0;i < q;i++) cin >> a[i];
	for(int i = 0;i < mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			for(int k = 0;k < 4;k++){
				int nx = i + dx[k],ny = j + dy[k];
				if(nx >= 0 && nx < m && ny >= 0 && ny < 7){
					if(!fnd((nx * 7 + ny) % m)) unite(i * 7 + j,nx * 7 + ny);
				}
			}
		}
	}
	set<int> st;
	for(int i = 0;i < mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			st.insert(find(i * 7 + j));
		}
	}
	n1 = st.size();
	if((m % 7 && n <= m) || (m % 7 == 0 && nn == 1)){
		cout << n1 << endl;
		return 0;
	}
	init(m * 14);
	for(int i = 0;i < 2 * mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			for(int k = 0;k < 4;k++){
				int nx = i + dx[k],ny = j + dy[k];
				if(nx >= 0 && nx < 2 * m && ny >= 0 && ny < 7){
					if(!fnd((nx * 7 + ny) % m)) unite(i * 7 + j,nx * 7 + ny);
				}
			}
		}
	}
	st.clear();
	for(int i = 0;i < 2 * mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			st.insert(find(i * 7 + j));
		}
	}
	n2 = st.size();
	if(m % 7) cout << n1 + (n2 - n1) * (n / m - 1) << endl;
	else cout << n1 + (n2 - n1) * (nn - 1) << endl;
	return 0;
}
### 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<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
 
using namespace std;
 
#define int long long
//typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD = 1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int par[1400001];
int rnk[1400001];

void init(int n){
	for(int i = 0;i < n;i++){
		par[i] = i;
		rnk[i] = 0;
	}
}

int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int x,int y){
	return find(x) == find(y);
}

int n,m,q;
int a[100000];

bool fnd(int x){
	return upper_bound(a,a + q,x) - lower_bound(a,a + q,x);
}

signed main(){
	int n1,n2;
	cin >> n >> m >> q;
	init(m * 7);
	int nn,mm;
	if(m % 7 == 0){
		nn = n / (m / 7);
		mm = m / 7;
	}
	else{
		nn = n;
		mm = m;
	}
	for(int i = 0;i < q;i++) cin >> a[i];
	for(int i = 0;i < mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			for(int k = 0;k < 4;k++){
				int nx = i + dx[k],ny = j + dy[k];
				if(nx >= 0 && nx < m && ny >= 0 && ny < 7){
					if(!fnd((nx * 7 + ny) % m)) unite(i * 7 + j,nx * 7 + ny);
				}
			}
		}
	}
	set<int> st;
	for(int i = 0;i < mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			st.insert(find(i * 7 + j));
		}
	}
	n1 = st.size();
	if((m % 7 && n <= m) || (m % 7 == 0 && nn == 1)){
		cout << n1 << endl;
		return 0;
	}
	init(m * 14);
	for(int i = 0;i < 2 * mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			for(int k = 0;k < 4;k++){
				int nx = i + dx[k],ny = j + dy[k];
				if(nx >= 0 && nx < 2 * m && ny >= 0 && ny < 7){
					if(!fnd((nx * 7 + ny) % m)) unite(i * 7 + j,nx * 7 + ny);
				}
			}
		}
	}
	st.clear();
	for(int i = 0;i < 2 * mm;i++){
		for(int j = 0;j < 7;j++){
			if(fnd((i * 7 + j) % m)) continue;
			st.insert(find(i * 7 + j));
		}
	}
	n2 = st.size();
	if(m % 7) cout << n1 + (n2 - n1) * (n / m - 1) << endl;
	else cout << n1 + (n2 - n1) * (nn - 1) << endl;
	return 0;
}
```