#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;

long long int n;
int m;
int q;

#define MAX 1000002
int room[MAX][7];
int id[MAX][7];

bool flag[MAX];

struct UF{
	vector<int> belong;
	vector<int> size;
	void resize(int n){
		belong.assign(n + 1, -1);
		size.assign(n + 1, 1);
	}
	inline int root(int b){
		if (belong[b] == -1){
			return b;
		}
		belong[b] = root(belong[b]);
		return belong[b];
	}
	void merge(int a, int b){
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (a < b)swap(a, b);
		belong[a] = b;
		size[b] += size[a];
	}
};
UF uf;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

vector<int> v;

void solve(int N){
	long long int sum = 0;
	if (n <= v.size()){
		for (int i = 0; i < n; i++){
			sum += v[i];
		}
		printf("%lld\n", sum);
		return;
	}
	long long int W = 0;
	for (int i = 1; i < v.size(); i++){
		W += v[i];
	}
	n--;
	W *= (n / N);
	n %= N;
	for (int i = 1; i <= n; i++){
		W += v[i];
	}
	W += v[0];
	printf("%lld\n", W);
}
int main(){
	cin >> n >> m >> q;
	for (int i = 0; i < q; i++){
		int a;
		scanf("%d", &a);
		flag[a] = true;
	}
	int num = -1;
	int nnn = -1;
	int N;
	bool exi = false;
	for (int i = 0; i < MAX; i++){
		for (int j = 0; j < 7; j++){
			num++;
			nnn++;
			id[i][j] = nnn;
			num %= m;
			if (i && (j == 0 && num == 0)){
				N = i;
				for (int j = 0; j < 7; j++){
					room[i][j] = room[0][j];
					id[i][j] = nnn;
					nnn++;
				}
				exi = true;
				break;
			}
			if (flag[num]){
				room[i][j] = true;
			}
		}
		if (exi)break;
	}
	if (0){

	}
	else{
		uf.resize(7 * (N+1));
		for (int i = 0; i <= N; i++){
			for (int j = 0; j < 7; j++){
				if (room[i][j] == true)continue;
				for (int k = 0; k < 4; k++){
					int ii = i + dx[k];
					int jj = j + dy[k];
					if (ii >= 0 && jj >= 0 && ii <= N&&jj < 7){
						if (room[i][j] == false && room[ii][jj] == false){
							uf.merge(id[i][j], id[ii][jj]);
						}
					}
				}
			}
		}
		for (int i = 0; i <= N; i++){
			int inc = 0;
			for (int j = 0; j < 7; j++){
				if (room[i][j] == false){
					if (uf.root(id[i][j]) == id[i][j]){
						inc++;
					}
				}
			}
			v.push_back(inc);
		}
		solve(N);
	}
	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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>
#include<unordered_set>
#include<unordered_map>
using namespace std;

long long int n;
int m;
int q;

#define MAX 1000002
int room[MAX][7];
int id[MAX][7];

bool flag[MAX];

struct UF{
	vector<int> belong;
	vector<int> size;
	void resize(int n){
		belong.assign(n + 1, -1);
		size.assign(n + 1, 1);
	}
	inline int root(int b){
		if (belong[b] == -1){
			return b;
		}
		belong[b] = root(belong[b]);
		return belong[b];
	}
	void merge(int a, int b){
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (a < b)swap(a, b);
		belong[a] = b;
		size[b] += size[a];
	}
};
UF uf;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

vector<int> v;

void solve(int N){
	long long int sum = 0;
	if (n <= v.size()){
		for (int i = 0; i < n; i++){
			sum += v[i];
		}
		printf("%lld\n", sum);
		return;
	}
	long long int W = 0;
	for (int i = 1; i < v.size(); i++){
		W += v[i];
	}
	n--;
	W *= (n / N);
	n %= N;
	for (int i = 1; i <= n; i++){
		W += v[i];
	}
	W += v[0];
	printf("%lld\n", W);
}
int main(){
	cin >> n >> m >> q;
	for (int i = 0; i < q; i++){
		int a;
		scanf("%d", &a);
		flag[a] = true;
	}
	int num = -1;
	int nnn = -1;
	int N;
	bool exi = false;
	for (int i = 0; i < MAX; i++){
		for (int j = 0; j < 7; j++){
			num++;
			nnn++;
			id[i][j] = nnn;
			num %= m;
			if (i && (j == 0 && num == 0)){
				N = i;
				for (int j = 0; j < 7; j++){
					room[i][j] = room[0][j];
					id[i][j] = nnn;
					nnn++;
				}
				exi = true;
				break;
			}
			if (flag[num]){
				room[i][j] = true;
			}
		}
		if (exi)break;
	}
	if (0){

	}
	else{
		uf.resize(7 * (N+1));
		for (int i = 0; i <= N; i++){
			for (int j = 0; j < 7; j++){
				if (room[i][j] == true)continue;
				for (int k = 0; k < 4; k++){
					int ii = i + dx[k];
					int jj = j + dy[k];
					if (ii >= 0 && jj >= 0 && ii <= N&&jj < 7){
						if (room[i][j] == false && room[ii][jj] == false){
							uf.merge(id[i][j], id[ii][jj]);
						}
					}
				}
			}
		}
		for (int i = 0; i <= N; i++){
			int inc = 0;
			for (int j = 0; j < 7; j++){
				if (room[i][j] == false){
					if (uf.root(id[i][j]) == id[i][j]){
						inc++;
					}
				}
			}
			v.push_back(inc);
		}
		solve(N);
	}
	return 0;
}
```