#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
ll N;
int M,Q;
const int MAX_M=1e5;
bool a[MAX_M];
bool flg[MAX_M*14];
void bfs(int s,int n){
	queue<int> que;
	que.push(s);
	flg[s]=true;
	while(!que.empty()){
		int v=que.front();
		que.pop();
		REP(dir,4){
			int v2=-1;
			switch(dir){
				case 0:
				if(v%7>0){
					v2=v-1;
				}
				break;
				case 1:
				if(v%7<6 && v+1<n){
					v2=v+1;
				}
				break;
				case 2:
				if(v>=7){
					v2=v-7;
				}
				break;
				case 3:
				if(v+7<n){
					v2=v+7;
				}
				break;
			}
			if(v!=-1 && !flg[v2] && !a[v2%M]){
				flg[v2]=true;
				que.push(v2);
			}
		}
	}
}
ll cntcon(int n){
	ll ret=0;
	memset(flg,false,sizeof(flg));
//	cout<<"cntcon "<<n<<endl;
	REP(i,n){
//		cout<<i<<" ";
		if(!flg[i] && !a[i%M]){
			ret++;
			bfs(i,n);
		}
	}
//	cout<<endl;
	return ret;
}

int main(){
	cin>>N>>M>>Q;
	REP(i,Q){
		int ta;
		cin>>ta;
		a[ta]=true;
	}
	if(N<M){
		cout<<cntcon(7*N)<<endl;
	}else{
		ll k=N/M;
		ll c1=cntcon(7*M),c2=cntcon(14*M);
		cout<<c1+(k-1)*(c2-c1)+cntcon((int)(7*N-7*k*M+7*M))-c1<<endl;
	}
}
### Prompt

Develop a solution in Cpp 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>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
ll N;
int M,Q;
const int MAX_M=1e5;
bool a[MAX_M];
bool flg[MAX_M*14];
void bfs(int s,int n){
	queue<int> que;
	que.push(s);
	flg[s]=true;
	while(!que.empty()){
		int v=que.front();
		que.pop();
		REP(dir,4){
			int v2=-1;
			switch(dir){
				case 0:
				if(v%7>0){
					v2=v-1;
				}
				break;
				case 1:
				if(v%7<6 && v+1<n){
					v2=v+1;
				}
				break;
				case 2:
				if(v>=7){
					v2=v-7;
				}
				break;
				case 3:
				if(v+7<n){
					v2=v+7;
				}
				break;
			}
			if(v!=-1 && !flg[v2] && !a[v2%M]){
				flg[v2]=true;
				que.push(v2);
			}
		}
	}
}
ll cntcon(int n){
	ll ret=0;
	memset(flg,false,sizeof(flg));
//	cout<<"cntcon "<<n<<endl;
	REP(i,n){
//		cout<<i<<" ";
		if(!flg[i] && !a[i%M]){
			ret++;
			bfs(i,n);
		}
	}
//	cout<<endl;
	return ret;
}

int main(){
	cin>>N>>M>>Q;
	REP(i,Q){
		int ta;
		cin>>ta;
		a[ta]=true;
	}
	if(N<M){
		cout<<cntcon(7*N)<<endl;
	}else{
		ll k=N/M;
		ll c1=cntcon(7*M),c2=cntcon(14*M);
		cout<<c1+(k-1)*(c2-c1)+cntcon((int)(7*N-7*k*M+7*M))-c1<<endl;
	}
}
```