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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

struct UnionFind{
	vector<int> par,rank;
	UnionFind(int n) :par(n + 1),rank(n + 1,1){
		for(int i = 1;i <= n;i++) par [i] = i;
	}
	int find(int x){
		return par [x] == x ? x : par [x] = find(par [x]);
	}
	bool connect(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(rank [x] < rank [y]) swap(x,y);
		rank [x] += rank [x] == rank [y];
		par [y] = x;
		return true;
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
};

ll N,M,Q;
set<int> st;

int main()
{
	scanf("%lld%lld%lld",&N,&M,&Q);
	FOR(i,0,Q){
		int x;
		scanf("%d",&x);
		st.insert(x);
	}
	int repeat;
	if(M % 7 == 0){
		repeat = M / 7;
	}
	else{
		repeat = M;
	}

	UnionFind uf(repeat * 7 * 2);
	vector<string> S(repeat,string(7,'x')),T(repeat,string(7,'x'));
	FOR(i,0,repeat) FOR(j,0,7) if(st.count((i * 7 + j) % M) == 0){
		S [i] [j] = 'o';
		T [i] [j] = 'o';
		if(i && S [i - 1] [j] == 'o'){
			uf.connect((i - 1) * 7 + j,i * 7 + j);
			uf.connect((i - 1) * 7 + j + (repeat * 7),i * 7 + j + (repeat * 7));
		}
		if(j && S [i] [j - 1] == 'o'){
			uf.connect(i * 7 + (j - 1),i * 7 + j);
			uf.connect(i * 7 + (j - 1) + (repeat * 7),i * 7 + j + (repeat * 7));
		}
	}

	ll ans = 0;
	FOR(i,0,repeat) FOR(j,0,7) if(S [i] [j] == 'o' && uf.find((i * 7 + j)) == i * 7 + j){
		ans += N / repeat;
	}
	FOR(i,0,7) if(S.front() [i] == 'o' && S.back() [i] == 'o'){
		if(uf.connect((repeat - 1) * 7 + i,i + (repeat * 7))){
			ans -= N / repeat - 1;
		}
	}

	printf("%lld\n",ans);

	return 0;
}

### Prompt

Please formulate 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;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

struct UnionFind{
	vector<int> par,rank;
	UnionFind(int n) :par(n + 1),rank(n + 1,1){
		for(int i = 1;i <= n;i++) par [i] = i;
	}
	int find(int x){
		return par [x] == x ? x : par [x] = find(par [x]);
	}
	bool connect(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(rank [x] < rank [y]) swap(x,y);
		rank [x] += rank [x] == rank [y];
		par [y] = x;
		return true;
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
};

ll N,M,Q;
set<int> st;

int main()
{
	scanf("%lld%lld%lld",&N,&M,&Q);
	FOR(i,0,Q){
		int x;
		scanf("%d",&x);
		st.insert(x);
	}
	int repeat;
	if(M % 7 == 0){
		repeat = M / 7;
	}
	else{
		repeat = M;
	}

	UnionFind uf(repeat * 7 * 2);
	vector<string> S(repeat,string(7,'x')),T(repeat,string(7,'x'));
	FOR(i,0,repeat) FOR(j,0,7) if(st.count((i * 7 + j) % M) == 0){
		S [i] [j] = 'o';
		T [i] [j] = 'o';
		if(i && S [i - 1] [j] == 'o'){
			uf.connect((i - 1) * 7 + j,i * 7 + j);
			uf.connect((i - 1) * 7 + j + (repeat * 7),i * 7 + j + (repeat * 7));
		}
		if(j && S [i] [j - 1] == 'o'){
			uf.connect(i * 7 + (j - 1),i * 7 + j);
			uf.connect(i * 7 + (j - 1) + (repeat * 7),i * 7 + j + (repeat * 7));
		}
	}

	ll ans = 0;
	FOR(i,0,repeat) FOR(j,0,7) if(S [i] [j] == 'o' && uf.find((i * 7 + j)) == i * 7 + j){
		ans += N / repeat;
	}
	FOR(i,0,7) if(S.front() [i] == 'o' && S.back() [i] == 'o'){
		if(uf.connect((repeat - 1) * 7 + i,i + (repeat * 7))){
			ans -= N / repeat - 1;
		}
	}

	printf("%lld\n",ans);

	return 0;
}

```