#include "bits/stdc++.h"
using namespace std;
const int M = 7e5 + 5;
long long n;
int m , q;
int mark[M];
int inp;
struct data{
	int top[7];
	int bot[7];
	long long ans;
	void compress(){
		map < int , int > mp;
		mp.clear();
		for(int i = 0 ; i < 7 ; ++i){
			if(top[i] != -1){
				mp[top[i]];
			}
			if(bot[i] != -1){
				mp[bot[i]];
			}
		}
		int val = 0;
		for(auto &it : mp){
			it.second = val++;
		}
		for(int i = 0 ; i < 7 ; ++i){
			if(top[i] != -1){
				top[i] = mp[top[i]];
			}
			if(bot[i] != -1){
				bot[i] = mp[bot[i]];
			}
		}
	}
};
int parent[M];
int find(int node){
	if(parent[node] == node){
		return node;
	}
	return parent[node] = find(parent[node]);
}
bool join(int a , int b){
	if(find(a) == find(b)){
		return 0;
	}
	parent[find(a)] = find(b);
	return 1;
}
data getbase(){
	for(int i = 0 ; i < m ; ++i){
		parent[i] = i;
	}
	int ans = m - q;
	for(int i = 0 ; i < m ; ++i){
		if(!mark[i]){
			if(i % 7 != 6 && !mark[i + 1]){
				ans -= join(i , i + 1);
			}
			if(i + 7 < m && !mark[i + 7]){
				ans -= join(i , i + 7);
			}
		}
	}
	data res;
	for(int i = 0 ; i < 7 ; ++i){
		if(mark[i]){
			res.top[i] = -1;
		}
		else{
			res.top[i] = find(i);
		}
	}
	for(int i = m - 7 ; i < m ; ++i){
		if(mark[i]){
			res.bot[i - m + 7] = -1;
		}
		else{
			res.bot[i - m + 7] = find(i);
		}
	}
	res.ans = ans;
	res.compress();
	return res;
}
data base;
data combine(data lft , data rgt){
	for(int i = 0 ; i < 30 ; ++i){
		parent[i] = i;
	}
	for(int i = 0 ; i < 7 ; ++i){
		if(rgt.top[i] != -1){
			rgt.top[i] += 14;
		}
		if(rgt.bot[i] != -1){
			rgt.bot[i] += 14;
		}
	}
	data res;
	res.ans = lft.ans + rgt.ans;
	for(int i = 0 ; i < 7 ; ++i){
		if(lft.bot[i] != -1 && rgt.top[i] != -1){
			res.ans -= join(lft.bot[i] , rgt.top[i]);
		}
	}
	for(int i = 0 ; i < 7 ; ++i){
		if(lft.top[i] == -1){
			res.top[i] = -1;
		}
		else{
			res.top[i] = find(lft.top[i]);
		}
		if(rgt.bot[i] == -1){
			res.bot[i] = -1;
		}
		else{
			res.bot[i] = find(rgt.bot[i]);
		}
	}
	res.compress();
	return res;
}
data solve(long long n){
	if(n == 1){
		return base;
	}
	if(n & 1){
		return combine(solve(n - 1) , base);
	}
	data tmp = solve(n >> 1);
	return combine(tmp , tmp);
}
int main(){
	scanf("%lld %d %d" , &n , &m , &q);
	for(int i = 1 ; i <= q ; ++i){
		scanf("%d" , &inp);
		mark[inp] = 1;
	}
	if(m % 7){
		for(int i = m ; i < m * 7 ; ++i){
			mark[i] = mark[i - m];
		}
		m *= 7;
		q *= 7;
	}
	base = getbase();
	printf("%lld\n" , solve((7 * n) / m).ans);
}
### Prompt

Generate 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 "bits/stdc++.h"
using namespace std;
const int M = 7e5 + 5;
long long n;
int m , q;
int mark[M];
int inp;
struct data{
	int top[7];
	int bot[7];
	long long ans;
	void compress(){
		map < int , int > mp;
		mp.clear();
		for(int i = 0 ; i < 7 ; ++i){
			if(top[i] != -1){
				mp[top[i]];
			}
			if(bot[i] != -1){
				mp[bot[i]];
			}
		}
		int val = 0;
		for(auto &it : mp){
			it.second = val++;
		}
		for(int i = 0 ; i < 7 ; ++i){
			if(top[i] != -1){
				top[i] = mp[top[i]];
			}
			if(bot[i] != -1){
				bot[i] = mp[bot[i]];
			}
		}
	}
};
int parent[M];
int find(int node){
	if(parent[node] == node){
		return node;
	}
	return parent[node] = find(parent[node]);
}
bool join(int a , int b){
	if(find(a) == find(b)){
		return 0;
	}
	parent[find(a)] = find(b);
	return 1;
}
data getbase(){
	for(int i = 0 ; i < m ; ++i){
		parent[i] = i;
	}
	int ans = m - q;
	for(int i = 0 ; i < m ; ++i){
		if(!mark[i]){
			if(i % 7 != 6 && !mark[i + 1]){
				ans -= join(i , i + 1);
			}
			if(i + 7 < m && !mark[i + 7]){
				ans -= join(i , i + 7);
			}
		}
	}
	data res;
	for(int i = 0 ; i < 7 ; ++i){
		if(mark[i]){
			res.top[i] = -1;
		}
		else{
			res.top[i] = find(i);
		}
	}
	for(int i = m - 7 ; i < m ; ++i){
		if(mark[i]){
			res.bot[i - m + 7] = -1;
		}
		else{
			res.bot[i - m + 7] = find(i);
		}
	}
	res.ans = ans;
	res.compress();
	return res;
}
data base;
data combine(data lft , data rgt){
	for(int i = 0 ; i < 30 ; ++i){
		parent[i] = i;
	}
	for(int i = 0 ; i < 7 ; ++i){
		if(rgt.top[i] != -1){
			rgt.top[i] += 14;
		}
		if(rgt.bot[i] != -1){
			rgt.bot[i] += 14;
		}
	}
	data res;
	res.ans = lft.ans + rgt.ans;
	for(int i = 0 ; i < 7 ; ++i){
		if(lft.bot[i] != -1 && rgt.top[i] != -1){
			res.ans -= join(lft.bot[i] , rgt.top[i]);
		}
	}
	for(int i = 0 ; i < 7 ; ++i){
		if(lft.top[i] == -1){
			res.top[i] = -1;
		}
		else{
			res.top[i] = find(lft.top[i]);
		}
		if(rgt.bot[i] == -1){
			res.bot[i] = -1;
		}
		else{
			res.bot[i] = find(rgt.bot[i]);
		}
	}
	res.compress();
	return res;
}
data solve(long long n){
	if(n == 1){
		return base;
	}
	if(n & 1){
		return combine(solve(n - 1) , base);
	}
	data tmp = solve(n >> 1);
	return combine(tmp , tmp);
}
int main(){
	scanf("%lld %d %d" , &n , &m , &q);
	for(int i = 1 ; i <= q ; ++i){
		scanf("%d" , &inp);
		mark[inp] = 1;
	}
	if(m % 7){
		for(int i = m ; i < m * 7 ; ++i){
			mark[i] = mark[i - m];
		}
		m *= 7;
		q *= 7;
	}
	base = getbase();
	printf("%lld\n" , solve((7 * n) / m).ans);
}
```